CF209C Trails and Glades

Vasya 在公园散步。公园里有 $n$ 个草地，编号从 $1$ 到 $n$。草地之间有 $m$ 条小路。这些小路也编号，从 $1$ 到 $m$，其中第 $i$ 条小路连接草地 $x_i$ 和 $y_i$。被连接的两个草地的编号可能相同（即 $x_i=y_i$），这表示该小路连接的是同一个草地。此外，任意两片草地之间可能存在多条互不相交的小路。 Vasya 现在位于第 $1$ 号草地，他希望能恰好一次性走遍公园里的所有小路，并最终回到第 $1$ 号草地。不幸的是，Vasya 并不确定这是否可行。请帮助 Vasya 判断，能否实现这样的行走。如果不能，请计算最少需要再修建多少条小路，才能使得上述行走变为可能。 Vasya 只可以在草地上更换小路。他可以在小路上来回行走。如果 Vasya 从某个连接草地 $a$ 和 $b$ 的小路，从 $a$ 出发，那么他必须走到 $b$ 结束。

第一行包含两个整数 $n$ 和 $m$，$1\le n\le 10^{6}$，$0\le m\le 10^{6}$，分别表示公园中的草地数和小路数。接下来 $m$ 行，每行两个用空格分隔的整数 $x_i, y_i$，$1\le x_i, y_i\le n$，表示第 $i$ 条小路连接的两个草地编号。

请输出一个整数，表示答案。如果不需要新修建小路即可完成行走，输出 $0$；否则输出最少需要新修建的小路数。

在第一个测试用例中，可以不用新建小路即可实现题目的行走要求。例如，可以先走第一条小路，再走第二条，最后走第三条。 在第二个测试用例中，不新建小路无法完成题目要求。要满足条件，只需再新建一条小路，比如在第 $1$ 号和第 $2$ 号草地之间再建一条。 由 ChatGPT 5 翻译