A6425. 「USACO 2022.12 Platinum」Making Friends
编程题
提高+/省选-
知识点
题目描述
**题目来自 [USACO 2022 December Contest, Platinum](http://usaco.org/index.php?page=dec22results) Problem 2. [Making Friends](http://usaco.org/index.php?page=viewproblem2&cpid=1261)**
FJ 的 $N$（$2\le N\le 2\cdot 10^5$）头编号为 $1\ldots N$ 的奶牛之中初始时有 $M$（$1\le M\le 2\cdot 10^5$）对朋友。奶牛们一头一头地离开农场去度假。第 $i$ 天，第 $i$ 头奶牛离开了农场，同时第 $i$ 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系？
FJ 的 $N$（$2\le N\le 2\cdot 10^5$）头编号为 $1\ldots N$ 的奶牛之中初始时有 $M$（$1\le M\le 2\cdot 10^5$）对朋友。奶牛们一头一头地离开农场去度假。第 $i$ 天，第 $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$）。每个奶牛无序对至多出现一次。
接下来 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 是朋友（$1\le u_i,v_i\le N$，$u_i\neq v_i$）。每个奶牛无序对至多出现一次。
输出格式
输出一行，包含形成的新的朋友关系的总数。不要计入初始时已经是朋友的奶牛对。
输入输出样例
输入 #1
7 6 1 3 1 4 7 1 2 3 2 4 3 5
输出 #1
5
说明/提示
- 测试点 2-3 满足 $N\le 500$。
- 测试点 4-7 满足 $N\le 10^4$。
- 测试点 8-17 没有额外限制。
- 测试点 4-7 满足 $N\le 10^4$。
- 测试点 8-17 没有额外限制。