Note: the time limit for this problem is 3s, 50% larger than the default.
The memory limit is twice the default.
There are initially $M$ ($1\le M\le 2\cdot 10^5$) pairs of friends among FJ's
$N$ ($2\le N\le 2\cdot 10^5$) cows labeled $1\dots 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 FORMAT (input arrives from the terminal / stdin):
The first line contains $N$ and $M$.

The next $M$ lines contain two integers $u_i$ and $v_i$ denoting that cows $u_i$
and $v_i$ are friends ($1\le u_i,v_i\le N$, $u_i\neq v_i$). 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 $1$, three new friendships are formed: $(3,4)$, $(3,7)$, and $(4,7)$.

On day $3$, two new friendships are formed: $(4,5)$ and $(5,7)$.

SCORING:
Test cases 2-3 satisfy $N\le 500$.Test cases 4-7 satisfy $N\le 10^4$.Test cases 8-17 satisfy no additional constraints.

Problem credits: Benjamin Qi

见题面

见题面