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
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
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