Making Friends

题目描述

注意：本题时间限制为 3s，比默认值增加 50%。 内存限制为默认值的两倍。 最初，在 FJ 的 $N$（$2\le N\le 2\cdot 10^5$）头奶牛（编号为 $1\dots N$）之间有 $M$（$1\le M\le 2\cdot 10^5$）对好友关系。奶牛们会依次离开农场去度假。在第 $i$ 天，第 $i$ 头奶牛离开农场，并且该奶牛仍然留在农场上的所有好友两两之间都会成为好友。 总共会形成多少对新的好友关系？

输入格式

第一行包含 $N$ 和 $M$。 接下来 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 是好友（$1\le u_i,v_i\le N$, $u_i\neq v_i$）。任意一对无序奶牛对不会出现超过一次。

输出格式

输出一行，包含形成的新好友关系总数。不应计入一开始就已经是好友的奶牛对。

7 6
1 3
1 4
7 1
2 3
2 4
3 5

5

提示

在第 $1$ 天，会形成三对新好友关系：$(3,4)$、$(3,7)$ 和 $(4,7)$。 在第 $3$ 天，会形成两对新好友关系：$(4,5)$ 和 $(5,7)$。 SCORING: 测试点 2-3 满足 $N\le 500$。 测试点 4-7 满足 $N\le 10^4$。 测试点 8-17 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum