问题7033--结交朋友

7033: 结交朋友

[命题人 : ]
时间限制 : 3.000 sec  内存限制 : 1024 MiB

题目描述

【题目描述】

FJ  N2≤N≤2×10^5)头编号为1…N 的奶牛之中初始时有 M1≤M≤2×10^5)对朋友。奶牛们一头一头地离开农场去度假。第 i 天,第 i 头奶牛离开了农场,同时第 i 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系?

输入格式(从终端 / 标准输入读入):

输入的第一行包含 N  M

以下 M 行每行包含两个整数 ui  vi,表示奶牛 ui  vi 是朋友(1≤ui,vi≤Nui≠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 没有额外限制。

 

 

样例输入 复制


样例输出 复制


来源/分类