#PU1261. USACO 2022 December Contest, Platinum — Problem 2. Making Friends

    ID: 1281 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec22来源:usaco.orgscoring:equal_test_cases并查集

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 MM (1≤M≤2⋅1051\le M\le 2\cdot 10^5) pairs of friends among FJ's NN (2≤N≤2⋅1052\le N\le 2\cdot 10^5) cows labeled 1…N1\dots N. The cows are leaving the farm for vacation one by one. On day ii, the ii-th cow leaves the farm, and all pairs of the ii-th cow's friends still present on the farm become friends. How many new friendships are formed in total?

输入格式

The first line contains NN and MM. The next MM lines contain two integers uiu_i and viv_i denoting that cows uiu_i and viv_i are friends (1≤ui,vi≤N1\le u_i,v_i\le N, ui≠viu_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.

数据范围

Test cases 2-3 satisfy N≤500N\le 500. Test cases 4-7 satisfy N≤104N\le 10^4. 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)$.