← 返回题目列表

Codeforces · 209/C

C. 小径和空地

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

Vasya 去公园散步。公园有 n 个空地,编号从 1 到 n。空地之间有 m 条小径。步道编号从 1 到 m,其中第 i 条步道连接空地 xi 和 yi。连接的林间空地的数量可能相同(xi = yi),这意味着一条路径将林间空地连接到其自身。此外,两个林间空地之间可能有几条不相交的小径。

Vasya 在 1 号林间空地,他想在公园的所有小径上只走一次,以便最终能够返回 1 号林间空地。不幸的是,Vasya 不知道这次步行是否可行。帮助 Vasya 确定步行是否可行。如果这样的步行是不可能的,请找出当局需要在公园中添加的最小步道数量,以使所描述的步行成为可能。

Vasya 只能在空地上从一条小路转移到另一条小路。他可以在小路上双向移动。如果 Vasya 从林间空地 a 开始走在连接林间空地 a 和 b 的小路上,那么他必须在林间空地 b 上完成这条小路。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 106; 0 ≤ m ≤ 106) — 分别是公园中的空地数量和公园中的步道数量。接下来的 m 行指定路径。第 i 行将第 i 条路径指定为两个以空格分隔的数字 xi, yi (1 ≤ xi, yi ≤ n) — 由该路径连接的林间空地的数量。

输出

打印单个整数——问题的答案。如果 Vasya 的步行无需添加额外的步道就可以实现,则打印 0,否则打印当局需要添加到公园中以使 Vasya 的步行成为可能的最小步道数。

示例

输入 #1

3 3
1 2
2 3
3 1

输出 #1

0

输入 #2

2 5
1 1
1 2
1 2
2 2
1 2

输出 #2

1

注意

在第一个测试用例中,无需建造额外的步道即可进行所描述的步行。例如,我们先走第一条路,然后走第二条路,最后走第三条路。

在第二个测试用例中,如果不添加额外的路径,所描述的步行是不可能的。为了使步行成为可能,添加一条小路就足够了,例如,在一号和二号空地之间添加一条小路。