*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?

Problem credits: Benjamin Qi

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

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.

One line containing the total number of new friendships formed. Do not include pairs of cows that
were already friends at the beginning.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > December > Platinum