#PU1261. USACO 2022 December Contest, Platinum — Problem 2. Making Friends
USACO 2022 December Contest, Platinum — Problem 2. Making Friends
USACO 2022 December Contest, Platinum — Problem 2. Making Friends
题目描述
Note: the time limit for this problem is 3s, 50% larger than the default. The memory limit is twice the default. There are initially () pairs of friends among FJ's () cows labeled . The cows are leaving the farm for vacation one by one. On day , the -th cow leaves the farm, and all pairs of the -th cow's friends still present on the farm become friends. How many new friendships are formed in total?
输入格式
The first line contains and . The next lines contain two integers and denoting that cows and are friends (, ). 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.
数据范围
Test cases 2-3 satisfy . Test cases 4-7 satisfy . Test cases 8-17 satisfy no additional constraints. Problem credits: Benjamin Qi
样例
样例 1
7 6
1 3
1 4
7 1
2 3
2 4
3 5
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)$.