Problems
There are initially M (1≤M≤2⋅105) pairs of friends among FJ's N (2≤N≤2⋅105) cows labeled 1…N.
The cows are leaving the farm for vacation one by one.
On day i, the i-th cow leaves the farm, and all pairs of the i-th cow's friends still present on the farm become friends. How many new friendships are formed in total?
Input
The first line contains N and M.
The next M lines contain two integers ui and vi denoting that cows ui and vi are friends (1≤ui,vi≤N, ui≠vi). No unordered pair of cows appears more than once.
Output
One line containing the total number of new friendships formed. Do not include pairs of cows that were already friends at the beginning.
Example
7 6
1 3
1 4
7 1
2 3
2 4
3 5
5
Tag
Source
USACO 2022 December Platinum
You must sign in to write code.