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 翻译