AT_xmascon22_h Happy Game

对于每个输入文件，有 $T$ 组测试数据。每组测试数据给定一个如下的图 $G$，请回答以下问题。 $G$ 是一个包含 $N$ 个顶点和 $M$ 条边的连通简单无向图。顶点编号为 $1$ 至 $N$，第 $i$ 条边连接顶点 $A_i$ 与 $B_i$（$1 \le i \le M$）。 现在，$G$ 的所有顶点均被涂成白色。接下来，“くろうさ”与“しろうさ”进行如下游戏： 1. 首先，“くろうさ”任选一个顶点，将其染成黑色。 2. 随后，只要仍有白色顶点存在，“しろうさ”不断进行如下操作： - 从所有和黑色顶点相邻的白色顶点中，任选 $1$ 个或 $2$ 个，将它们全部染成黑色。 “しろうさ”的操作次数称为**得分**。くろうさ的目标是最大化得分，しろうさ的目标是最小化得分。若双方均采取最优策略，求该游戏的得分。

第一行为测试数据组数 $T$。 接下来每组测试数据格式如下： > $N$ $M$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_M$ $B_M$

对于每组测试数据，输出一行答案。

### 样例解释 1 对于第 $1$ 个测试数据，くろうさ选择顶点 $1$ 或 $3$，しろうさ最少操作 $2$ 次即可完成。 对于第 $2$ 个测试数据，くろうさ选哪个顶点都一样，しろうさ也只需操作 $2$ 次即可完成。 ### 约束条件 - $1 \le T \le 1.5 \times 10^5$。 - $2 \le N \le 3 \times 10^5$。 - $N-1 \le M \le 3 \times 10^5$。 - $1 \le A_i,B_i \le N$，$1 \le i \le M$。 - 图 $G$ 是简单且连通的。 - 输入文件中所有 $N$ 之和不超过 $3 \times 10^5$。 - 输入文件中所有 $M$ 之和不超过 $3 \times 10^5$。 由 ChatGPT 5 翻译