Programming Assignment 3

The World Chess Federation (F.I.D.E) are planning the World Chess Championship. tournament. One of the constraints they need to respect is to pair

chess players from different countries. There are N professional chess players

numbered from 0 to N − 1 . FIDE does not have information about the citizenship of each chess player but they do know have some information about which

players belong to the same country. Your task is to compute the number of

ways possible to play a match between 2 players from different countries. You

are provided with enough number of pairs so you succeed in your mission even

though you don’t know their citizenship right away. For example, if the players

1 , 2 and 3 are from the same country then the 2 pairs (1, 2) and (2, 3) give

sufficient information and the third pair (1, 3) is not needed.

1 Input and Output

The first line contains two integers, N and I separated by a single space. I lines

follow. Each line contains 2 integers A and B separated by a single space such

that

0 ≤ A, B ≤ N − 1

1 ≤ N ≤ 105

1 ≤ I ≤ 104

A and B are chess players from the same country. The input should be taken

from a separate input file. The output should be a single line displaying the

number of permissible ways to choose a pair of chess players. There is no need

to write it in a separate output file. You can display it on the console.

2 Sample Input

5 2

0 1

2 3

1

3 Sample Output

8

4 Explanation

We have the following pairs (0, 2),(0, 3),(1, 2),(1, 3),(0, 4),(1, 4),(2, 4),(3, 4) where

players are from different countries in each pair.

2