← 返回题目列表

AtCoder · xmascon22_h

H. 快乐游戏

中文机器翻译题面 查看原题

配点 : 100 点

黑兔“今年要多操作哦!”

白兔“很温柔”

問題文

1 每个输入文件 T 有若干测试用例。每个测试用例中有如下图形 G ,回答以下问题。

G 是 您也可以写 N 頂点 M 由边组成的连通简单无向图。顶点通过 1 减去 N 。i 第一条边是顶点 A_i 和 按字典顺序比较 B_i 相连 (1 \le i \le M).

今,G 的所有顶点都被涂成白色)。从这里开始,黑兔和白兔进行以下游戏。

  1. 首先,黑兔选择自己喜欢的 1 个顶点,并将其涂成黑色。
  2. 然后,只要存在被涂成白色的顶点,白兔重复以下操作:
    • 选择与黑色顶点相邻的 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