1530：Ant Trip

题目描述

给你无向图的 $N$ 个点和 $M$ 条边，保证这 $M$ 条边都不同且不会存在同一点的自环边，现在问你至少要几笔才能所有边都画一遍。（一笔画的时候笔不离开纸）

输入格式

多组数据，每组数据用空行隔开。

对于每组数据，第一行两个整数 $N, M$ 表示点数和边数。接下去 $M$ 行每行两个整数 $a, b$，表示 $a, b$ 之间有一条边。

输出格式

对于每组数据，输出答案。

样例

样例输入 #1

3 3
1 2
2 3
1 3

4 2
1 2
3 4

样例输出 #1

1
2

样例解释 #1

第一组数据：

• $N=3, M=3$，边：$1-2$, $2-3$, $1-3$。
• 这是一个三角形，每个顶点的度数均为 $2$（偶数），且图连通，所以存在欧拉回路，一笔画即可。输出 $1$。

第二组数据：

• $N=4, M=2$，边：$1-2$, $3-4$。
• 图有两个连通分量，每个连通分量都是一条边（两个顶点度数为 $1$，奇数）。每个连通分量需要一笔（因为奇数度顶点个数为 $2$，需要 $2/2=1$ 笔）。总笔数为两个分量笔数之和，即 $1+1=2$。输出 $2$。

数据范围

• $1 \le N \le 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le a, b \le N$

时空限制

• 时间限制：1000 ms
• 内存限制：32768 KB

注意：本题是计算无向图至少需要多少笔才能画完所有边（每条边只能画一次，笔不能离开纸，即每笔是一个欧拉路径/回路）。对于每个连通分量：

• 如果该分量没有边（孤立点），则不需要笔画（忽略）。
• 否则，设该连通分量中奇度顶点的个数为 $cnt$。如果 $cnt=0$，则该分量存在欧拉回路，需要 $1$ 笔。如果 $cnt>0$，则该分量需要 $\lfloor cnt/2 \rfloor$ 笔（因为每笔可以消除两个奇度顶点，实际上每笔对应一条欧拉路径，起点和终点是奇度顶点）。
• 因此，每个连通分量需要的笔画数为 $\max(1, cnt/2)$（因为当 $cnt=0$ 时取 $1$，$cnt>0$ 时取 $cnt/2$）。

总笔画数为所有连通分量的笔画数之和。注意孤立点（度数为 $0$）不计入连通分量（因为没有边）。由于 $N$ 和 $M$ 较大，需要用并查集维护连通分量，并统计每个连通分量中的奇度顶点个数。注意输入多组数据，用空行隔开，可能用 while(cin>>N>>M) 读取，需要处理空行。