USACO

USACO 2022 December Contest, Platinum

Problem 2. Making Friends

Contest has ended.

Log in to allow submissions in analysis mode

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

SAMPLE OUTPUT:

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

Contest has ended. No further submissions allowed.