配点 : 100 点
黑兔“今年要多操作哦!”
白兔“很温柔”
問題文
1 每个输入文件 T 有若干测试用例。每个测试用例中有如下图形 G ,回答以下问题。
G 是 您也可以写 N 頂点 M 由边组成的连通简单无向图。顶点通过 1 减去 N 。i 第一条边是顶点 A_i 和 按字典顺序比较 B_i 相连 (1 \le i \le M).
今,G 的所有顶点都被涂成白色)。从这里开始,黑兔和白兔进行以下游戏。
- 首先,黑兔选择自己喜欢的 1 个顶点,并将其涂成黑色。
- 然后,只要存在被涂成白色的顶点,白兔重复以下操作:
- 选择与黑色顶点相邻的 1 件或 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 是简单且连通的。
- 1 个输入文件中的 N 的总和是 3 \times 10^5 不超过。
- 1 个输入文件中的 M 的总和是 3 \times 10^5 不超过。
入力
标准输入 1 排队测试用例数 给出了 T 。之后,T 测试用例均按以下格式给出。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
关于各个测试用例,答案是 1 行输出。
入力例 1
2 3 2 1 2 2 3 4 4 1 2 2 3 3 4 4 1
出力例 1
2 2
1 在第几个测试用例中,通过黑兔选择顶点 1 或 至少 3 使白兔的操作次数为 2 次。
2 在第几测试用例中,无论黑兔选择哪个顶点,白兔的操作次数都是 2 次。
入力例 2
2 5 8 5 1 2 3 2 4 5 2 1 3 3 5 1 4 4 5 20 40 13 10 13 19 12 15 14 7 1 17 8 17 13 7 10 7 16 2 5 20 12 1 3 12 19 7 8 20 20 16 2 5 14 13 3 9 13 6 5 16 4 1 2 4 8 16 14 10 8 2 11 8 15 3 18 5 17 20 11 17 6 10 16 11 15 1 9 6 19 6 8 4 2 11 20 11 10 19 16 18
出力例 2
2 11