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?
Input
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.
Output
Print the required number of ways to choose villages for the festival.
Example
Input: 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
joysaha:
2024-08-21 18:20:26
bitset and O(n^2) |
|
vcode11:
2019-06-23 12:35:03
Represent sets as bits use bitsets in c++.
|
|
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)
|
Added by: | Adrian Satja Kurdija |
Date: | 2011-05-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Croatian junior team selection test 2011 |