VILLAGES - Villages by the River

In a far away country there is a wide river, N villages on the left and N villages on the right side of this river (denoted by 1..N on each side). There are also M small ships, each of them connecting one village from the left and one village from the right side (in both ways).

You are to organize a film festival in four of these villages: two from the left and two from the right side. Each two of these four villages must be connected by a ship (directly) if they belong to opposite sides of the river.

Help yourself to choose these four villages and first find out; in how many ways can you choose them?


In the first line there are integers N ≤ 1000 and M ≤ N2.

In the next M lines there are two integers from the interval [1, N] representing the village from the left and the village from the right side connected by this ship.


Print the required number of ways to choose villages for the festival.


3 5
1 1
1 2
1 3
2 2
2 3
Output: 1

(the only possibility is to choose the villages 1, 2 from the left and 2, 3 from the right side)

hide comments
vcode11: 2019-06-23 12:35:03

Represent sets as bits use bitsets in c++.

mahmud2690: 2016-10-14 17:12:00

Last edit: 2016-10-18 20:28:34
enigmus: 2016-10-11 14:28:21

Be sure to use bitmasks from cpp library which is heavily optimized. Passing solution is O(N^3).

$!:D: 2013-06-09 07:49:13

plzz someone suggest any approach to solve dis

Last edit: 2013-06-11 21:15:46
Termvader: 2012-08-07 02:19:54

I did this in O(n^3)
Is there anyway to do it in less complexity?

Added by:Adrian Satja Kurdija
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian junior team selection test 2011