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 ≤ N^{2}.
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
vcode11:
20190623 12:35:03
Represent sets as bits use bitsets in c++.


mahmud2690:
20161014 17:12:00
Last edit: 20161018 20:28:34 

enigmus:
20161011 14:28:21
Be sure to use bitmasks from cpp library which is heavily optimized. Passing solution is O(N^3). 

$!:D:
20130609 07:49:13
plzz someone suggest any approach to solve dis Last edit: 20130611 21:15:46 

Termvader:
20120807 02:19:54
I did this in O(n^3)

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