TSEC Codecell is organizing TSEC Hacks across different colleges.
There are N teams registered for the event, each identified by a unique ID from 0 to N-1.
We maintain a database of pairs of teams from the same college. Each record (A, B) means both teams are from the same college.
Now, the Codecell wants to form project pairs such that each pair consists of teams from different colleges — the goal is to encourage cross-college collaboration and diversity.
Your task is to determine how many unique pairs of Teams can be formed that meet this criterion.
Constraints
1 <= N <= 10^5
1 <= M <= 10^4
Input Format
First line: Two integers — N (number of teams) and M (number of same-college pair records)
Next M lines: Two integers A and B, representing teams from the same college.
Output Format
Print a single integer — the total number of valid team pairs from different college
Example 1
Input:
5 3
0 1
2 3
0 4
Output:
6
Explanation:
From this data:
Teams {0, 1, 4} belong to one college
Teams {2, 3} belong to another
Possible cross-college project pairs:
(0,2), (0,3), (1,2), (1,3), (4,2), (4,3)
Log In to solve the Question