P8907 [USACO22DEC] Making Friends P

Among FJ's $N(2 \le N \le 2 \times 10^5)$ cows numbered $1 \cdots N$, there are initially $M(1 \le M \le 2 \times 10^5)$ pairs of friends. The cows leave the farm one by one to go on vacation. On day $i$, cow $i$ leaves the farm, and at the same time, all of cow $i$'s friends that are still on the farm become friends with each other. How many new friendship relationships are created in total?

The first line contains $N$ and $M$. The next $M$ lines each contain two integers $u_i$ and $v_i$, meaning cows $u_i$ and $v_i$ are friends ($1 \le u_i,v_i \le N, u_i \neq v_i$). Each unordered pair of cows appears at most once.

Output one line containing the total number of new friendship relationships formed. Do not count pairs of cows that were already friends initially.

### Explanation for Sample 1 On day $1$, three new friendship relationships are created: $(3,4)$, $(3,7)$, and $(4,7)$. On day $3$, two new friendship relationships are created: $(4,5)$ and $(5,7)$. ### Test Point Properties - Test points $2-3$ satisfy $N \le 500$. - Test points $4-7$ satisfy $N \le 10^4$. - Test points $8-17$ have no additional constraints. Translated by ChatGPT 5