1533：相框

题目描述

P 大的基础电路实验课是一个无聊至极的课。每次实验，T 君总是提前完成，管理员却不让 T 君离开，T 君只能干坐在那儿无所事事。

先说说这个实验课，无非就是把几根导线和某些元器件（电阻、电容、电感等）用焊锡焊接起来。

为了打发时间，T 君每次实验做完后都在焊接一些诡异的东西，这就是他的杰作：

（示意图省略）

T 君不满足于焊接奇形怪状的作品，强烈的破坏欲驱使他拆掉这个作品，然后将之焊接成规整的形状。这会儿，T 君正要把这个怪物改造成一个环形，当作自己的相框。

T 君约定了两种操作：

1. 烧熔一个焊点：使得连接在焊点上的某些导线相分离或保持相连（可以理解为：把焊点上的导线划分为若干个类，相同类中的导线相连，不同类之间的导线相离）
2. 将两根导线的自由端（即未与任何导线相连的一端）焊接起来。

T 君想用最少的操作来将原有的作品改造成为相框（要用上所有的导线）。

输入格式

第一行共有两个整数 $n$ 和 $m$——分别表示原有的作品的焊点和导线的数量。焊点的标号为 $1 \sim n$。接下来的 $m$ 行每行共有两个整数——导线两端所连接的两个焊点的标号，若不与任何焊点相连，则将这一端标号为 $0$。

原有的作品可能不是连通的。

某些焊点可能只有一根导线与之相连，在该导线的这一端与其他导线相连之前，这些焊点不允许被烧熔。

某些焊点甚至没有任何导线与之相连，由于 T 君只关心导线，因此这些焊点可以不被考虑。

输出格式

只包含一个整数——表示 T 君需要将原有的作品改造成相框的最少步数。

样例

样例输入 #1

6 8
1 2
1 3
3 4
1 4
4 6
5 6
4 5
1 5

样例输出 #1

4

样例解释 #1

• $n=6$ 个焊点，$m=8$ 条导线。
• 导线连接：
  1. $1-2$
  2. $1-3$
  3. $3-4$
  4. $1-4$
  5. $4-6$
  6. $5-6$
  7. $4-5$
  8. $1-5$
• 目标是将所有导线连接成一个环（相框），且必须使用所有导线。
• 最少需要 $4$ 步操作。具体步骤可能包括烧熔某些焊点重新划分导线连接，以及焊接自由端。

数据范围

• 对于 $30\%$ 的数据，$n \le 10$
• 对于 $100\%$ 的数据，$0 \le n \le 1000$，$2 \le m \le 50000$

时空限制

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

注意：本题是欧拉回路/路径的变形问题。原图可以看作一个无向图，焊点是顶点，导线是边。目标是通过最少的操作将图变成一个欧拉回路（即一个环，每个顶点的度数均为偶数，且图连通）。操作 1（烧熔焊点）相当于将一个顶点分裂成多个顶点，从而改变顶点的度数奇偶性；操作 2（焊接自由端）相当于连接两个度数为奇数的顶点（即增加一条边）。

解题思路：

1. 统计每个连通分量。如果一个连通分量中所有顶点的度数均为偶数，那么该分量本身已经是欧拉图，不需要额外操作就可以形成环（但可能还需要与其他分量连接）。然而，目标是要将所有导线（边）连成一个环，即整个图连通且每个顶点度数为偶数。
2. 考虑将每个连通分量通过焊接自由端（添加边）连接起来，同时调整度数奇偶性。
3. 最少操作数 = 需要添加的边数 + 需要烧熔的焊点数。
4. 具体公式：设总奇度顶点数为 $odd$，连通块个数为 $block$，孤立点（度数为 $0$ 的顶点）不考虑。则最少操作数为 $odd/2 + \max(0, block-1)$？但还需要考虑烧熔操作。
5. 实际上，本题是经典问题：将任意无向图通过分裂顶点（烧熔）和加边（焊接）变成欧拉回路的最小操作数。结论：设原图有 $c$ 个连通分量，每个连通分量的奇度顶点数为 $odd_i$，则最少操作数为 $\sum \max(1, odd_i/2) + \max(0, c-1)$？需要验证。

由于 $n, m$ 较大，需要高效算法。可以用并查集维护连通分量，同时统计每个顶点的度数和每个连通分量的奇度顶点数。注意处理一端为 $0$ 的边（自由端），这种情况下，该边只连接一个焊点（另一端是自由端），相当于该焊点度数加 $1$，同时整个图增加一个自由端（可以与其他自由端焊接）。实际上，将 $0$ 视为一个特殊的焊点（自由端集合），但 $0$ 不计入 $n$。处理时，可以将 $0$ 看作一个额外的顶点，其度数就是自由端的数量。但焊接自由端相当于连接两个自由端（或一个自由端与一个焊点）形成一条新边，这属于操作 2。需要仔细分析。