Start: 2023-08-12 08:20:00

0812算法入门(2)期末测试

End: 2023-08-12 11:00:00
Now  2025-12-16 03:39:24  类型: IOI  状态: Ended 

P4. 消灭扫雷团伙
Description

W老师刚到学校,发现所有学生喜欢上课的时候玩扫雷,而且他们还喜欢组队玩,玩扫雷的同学慢慢会形成几个团体,W老师不能一开始就针对这些学生,他只能等扫雷小分队组成之后,逐个进行心理疏导,让他们在课上认真读书,所以W老师准备先找人少的团队进行疏导!

请你写一个程序,求出W老师要进行疏导的最大团队的人数!


Input

第一行两个数  

一个数N,表示这个班级有多少个学生,一个数M,表示扫雷小分队的组队情况  

接下来M组数据,每行三个数字u,v,分别表示学生u和学生v他们代表的队伍组成了一个更大的扫雷小分队!

由于关系的组队情况,最多有20W条,会有重复组队的情况出现的!请同学们注意,就是重复组队,队伍人数是不会变得!


Output

两个数字,表示W老师分别表示要约谈的团伙头目次数,以及最大团队的人数!

Examples

Input

5 3
1 2
1 3
5 4

Output

2 3
Hint

通过连接,他们形成了1-2-3一个小分队,还有4 5一个小分队,W老师会先解决4-5这个小分队,然后在解决1-2-3这个小分队,所以输出的是2.因为有两个团伙,他要约谈2次,而最大的团队是3个人。

ui,vi<=N<=10000 

M<=200000


Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit