← 返回题目列表

Codeforces · 191/D

D. 地铁方案

中文机器翻译题面 查看原题

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

注意

第二个样本的线路数量最少的地铁方案是: