Berland非常注重隐私,因此几乎所有计划和蓝图都是秘密的。然而,邻国的一名间谍成功窃取了伯敦地铁计划。
Bertown 地铁有 n 个车站,编号从 1 到 n,有 m 个双向隧道连接它们。所有 Bertown 地铁均由线路组成。更准确地说,有两种类型的线:圆形线和放射线。
径向线是一系列站点 v1, ..., vk (k > 1),其中站点 vi 和 vi + 1 (i < k) 通过隧道连接,并且线路中没有站点出现超过一次(vi ≠ vj,因为 i ≠ j)。
环线是一系列车站 v1, ..., vk (k > 2),其中车站 vi и vi + 1 通过隧道连接。另外,站v1和vk也通过隧道连接。环线上没有车站出现超过一次。
请注意,单个车站可以由任意多条线路经过。
根据 Berland 标准,两个车站之间不能有超过一条隧道,并且每条隧道恰好属于一条线路。当然,每条线路至少有一条隧道。任何两个车站之间都有一条沿着地铁隧道的路。此外,从图论的角度来看,地铁是一棵顶点仙人掌:如果我们将地铁视为一张图,其中车站是顶点,边是隧道,那么每个顶点不超过一个简单循环。
不幸的是,被间谍窃取的计划只有车站和隧道。无法确定每条隧道对应哪条线。但为了成功地进行破坏,间谍需要知道伯敦地铁的最小和最大线路数是多少。
帮助他!
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 3·105) — 相应的车站数量和隧道数量。
接下来的 m 行中的每一行都包含两个整数——相应隧道连接的车站数量。这些站用 1 到 n 的整数进行编号。
保证地铁对应的图没有重边或环,它是连通的,并且是一个顶点仙人掌。
输出
打印两个数字——相应的最小和最大行数。
示例
输入 #1
3 3 1 2 2 3 3 1
输出 #1
1 3
输入 #2
8 8 1 2 2 3 3 4 4 5 6 4 4 7 7 2 2 8
输出 #2
2 8
输入 #3
6 6 1 2 2 3 2 5 5 6 3 4 3 5
输出 #3
3 6
注意
第二个样本的线路数量最少的地铁方案是: