CF209C.Trails and Glades

Vasya went for a walk in the park. The park has n glades, numbered from 1 to n. There are m trails between the glades. The trails are numbered from 1 to m, where the i-th trail connects glades x__i and y__i. The numbers of the connected glades may be the same (x__i = y__i), which means that a trail connects a glade to itself. Also, two glades may have several non-intersecting trails between them.

Vasya is on glade 1, he wants to walk on all trails of the park exactly once, so that he can eventually return to glade 1. Unfortunately, Vasya does not know whether this walk is possible or not. Help Vasya, determine whether the walk is possible or not. If such walk is impossible, find the minimum number of trails the authorities need to add to the park in order to make the described walk possible.

Vasya can shift from one trail to another one only on glades. He can move on the trails in both directions. If Vasya started going on the trail that connects glades a and b, from glade a, then he must finish this trail on glade b.

瓦西娅去公园散步。公园里有 $n$ 个林间空地，编号从 $1$ 到 $n$。空地之间共有 $m$ 条小径，编号从 $1$ 到 $m$，其中第 $i$ 条小径连接空地 $x_i$ 和 $y_i$。所连接的两个空地编号可能相同（即 $x_i = y_i$），表示该小径是连接某个空地与其自身的环路。此外，两个空地之间可能存在多条互不相交的小径。

瓦西娅起始于空地 $1$，他希望恰好遍历公园中的每一条小径一次，并最终返回空地 $1$。然而，瓦西娅并不知道这样的行走路径是否存在。请帮助瓦西娅判断该行走路径是否可行。若不可行，请找出管理部门需在公园中最少添加多少条小径，才能使上述行走路径成为可能。

瓦西娅只能在空地上从小径切换到另一条小径。他可以沿任意方向通行各条小径。若瓦西娅从空地 $a$ 出发，沿连接空地 $a$ 与 $b$ 的小径开始行走，则他必须在空地 $b$ 处结束该小径的通行。

The first line contains two integers n and m (1 ≤ n ≤ 106; 0 ≤ m ≤ 106) — the number of glades in the park and the number of trails in the park, respectively. Next m lines specify the trails. The i-th line specifies the i-th trail as two space-separated numbers, x__i, y__i (1 ≤ x__i, y__i ≤ n) — the numbers of the glades connected by this trail.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^6$；$0 \leq m \leq 10^6$），分别表示公园中林间空地的数量和小径的数量。接下来的 $m$ 行描述这些小径。第 $i$ 行以两个用空格分隔的整数 $x_i$、$y_i$（$1 \leq x_i, y_i \leq n$）描述第 $i$ 条小径，表示该小径连接的两片林间空地的编号。

Print the single integer — the answer to the problem. If Vasya's walk is possible without adding extra trails, print 0, otherwise print the minimum number of trails the authorities need to add to the park in order to make Vasya's walk possible.

输出一个整数——即该问题的答案。如果瓦西娅的行走无需添加额外小径即可实现，则输出 0；否则，输出当局需在公园中添加的、使得瓦西娅的行走成为可能的最少小径数量。

In the first test case the described walk is possible without building extra trails. For example, let's first go on the first trail, then on the second one, and finally on the third one.

In the second test case the described walk is impossible without adding extra trails. To make the walk possible, it is enough to add one trail, for example, between glades number one and two.

在第一个测试用例中，无需修建额外的小径即可完成所述的行走。例如，我们可以先走第一条小径，再走第二条小径，最后走第三条小径。

在第二个测试用例中，若不添加额外的小径，则无法完成所述的行走。为使行走成为可能，只需添加一条小径即可，例如在编号为一和二的林间空地之间修建一条小径。