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
注意
在第一个测试用例中,无需建造额外的步道即可进行所描述的步行。例如,我们先走第一条路,然后走第二条路,最后走第三条路。
在第二个测试用例中,如果不添加额外的路径,所描述的步行是不可能的。为了使步行成为可能,添加一条小路就足够了,例如,在一号和二号空地之间添加一条小路。