许久以前,天下大乱,地球上的所有人划分成为了 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 |
提示
样例中 1 和 2 是朋友,3 和 5 是朋友,2 和 4 是朋友。
因此有 2 个敌对群体 (1,2,4),(3,5) 互相掐架的次数为 1 次。