Note: the time limit for this problem is 3s, 50% larger than the default. The memory limit is twice the default.
There are initially MM (1≤M≤2⋅1051≤M≤2⋅105) pairs of friends among FJ's NN (2≤N≤2⋅1052≤N≤2⋅105) cows labeled 1…N1…N. The cows are leaving the farm for vacation one by one. On day ii, the ii-th cow leaves the farm, and all pairs of the ii-th cow's friends still present on the farm become friends. How many new friendships are formed in total?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains NN and MM.The next MM lines contain two integers uiui and vivi denoting that cows uiui and vivi are friends (1≤ui,vi≤N1≤ui,vi≤N, ui≠viui≠vi). No unordered pair of cows appears more than once.
OUTPUT FORMAT (print output to the terminal / stdout):
One line containing the total number of new friendships formed. Do not include pairs of cows that were already friends at the beginning.
SAMPLE INPUT:
7 6
1 3
1 4
7 1
2 3
2 4
3 5
SAMPLE OUTPUT:
5
On day 11, three new friendships are formed: (3,4)(3,4), (3,7)(3,7), and (4,7)(4,7).
On day 33, two new friendships are formed: (4,5)(4,5) and (5,7)(5,7).
SCORING:
Test cases 2-3 satisfy N≤500N≤500.
Test cases 4-7 satisfy N≤104N≤104.
Test cases 8-17 satisfy no additional constraints.
Problem credits: Benjamin Qi