题目描述
【题目描述】
FJ 的 N(2≤N≤2×10^5)头编号为1…N 的奶牛之中初始时有 M(1≤M≤2×10^5)对朋友。奶牛们一头一头地离开农场去度假。第 i 天,第 i 头奶牛离开了农场,同时第 i 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系?
【输入格式】(从终端 / 标准输入读入):
输入的第一行包含 N 和 M。
以下 M 行每行包含两个整数 ui 和 vi,表示奶牛 ui 和 vi 是朋友(1≤ui,vi≤N,ui≠vi)。每个奶牛无序对至多出现一次。
【输出格式】(输出至终端 / 标准输出):
输出一行,包含形成的新的朋友关系的总数。不要计入初始时已经是朋友的奶牛对。
【输入样例】:
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)。
【测试点性质】:
测试点 2-3 满足 N≤500。
测试点 4-7 满足 N≤10^4。
测试点 8-17 没有额外限制。
样例输入 复制
样例输出 复制