2023 蓝桥杯热身赛

Problem P27. 好朋友

许久以前,天下大乱,地球上的所有人划分成为了 N 个群体,但是有些群体关系好,所以他们是好朋友,当然朋友的朋友也是朋友,如果这个两个群体不是朋友关系,那就是敌对关系,敌对关系的群体是会两两相互掐架的。

现在给出初始的 N 个群体,初始时所有人都是敌对关系,即都没有朋友,再给出 M 条友好交往记录,如果群体 i 和群体 j 有友好交流记录,那么他们会成为朋友。

你需要求出最终会有多少个敌对群体,以及这些所有群体会掐架的次数。

输入

输入第一行包含两个正整数 N,M \ (1≤N≤10^5,0≤M≤10^5)

接下来 M 行每行两个整数 i,j \ (1 \leq i,j \leq N),表示 M 条友好交流记录。

注意:输入数据中友好交往记录是可能重复的,而且 i=j 也是可能的。

输出

输出一行。

表示敌对群体的个数以及敌对群体掐架的次数,中间空格隔开。

样例

标准输入 复制文本
5 3
1 2
3 5
2 4
标准输出 复制文本
2 1

提示

样例中 12 是朋友,35 是朋友,24 是朋友。

因此有 2 个敌对群体 (1,2,4),(3,5) 互相掐架的次数为 1 次。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 54
通过 18