Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21726. 【CTS Round #1 Day 1】黑白点

统计

给定一张 $n$ 个点和 $m$ 条边的联通简单无向图,其中第 $i$($1 \le i \le m$)条边连接了顶点 $u_i$ 与 $v_i$($1 \le u_i, v_i \le n$)。

初始时,所有的顶点均为白色的。Alice 与 Bob 两名玩家将在上面玩一个游戏,游戏的规则如下:

  • 初始时,Alice 选择一个顶点 $x$($1 \le x \le n$),并将顶点 $x$ 涂为黑色。
  • 随后,Bob 将进行若干轮操作:
    • 每次 Bob 可以选择一个顶点两个顶点,满足这些顶点均为白色顶点,且每个顶点在此次操作之前均存在一个邻居顶点的颜色为黑色。
    • 将选择的这些顶点的颜色涂为黑色。
  • 当所有顶点的颜色均被涂成了黑色时,游戏结束。Bob 所消耗的时间为它进行的操作的轮数。

Bob 希望游戏尽可能快地结束,Alice 则希望游戏尽可能慢地结束。现在,你想要求,如果双方均采取最优策略,则游戏会在几个回合后结束。

输入格式

本题的每个测试点中可能包含多组测试数据。

输入的第一行包含一个整数 $T$,表示数据组数。

对于每组数据:

输入的第一行包含两个整数 $n$ 与 $m$,描述图的点数与边数。

接下来 $m$ 行,每行两个整数 $u, v$,描述一条边。

保证图中不存在重边与自环,且图为一张联通的无向图。

输出格式

对于每组数据,输出一行一个整数,表示答案。

样例数据

样例输入

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

样例输出

3
2
2

样例解释

对于第一组测试数据,Alice 的一种最优方案为选择顶点 $1$ 将其涂为黑色,此时:

  • 在第一轮时,Bob 选择顶点 $2$,并将其涂为黑色。
  • 在第二轮时,Bob 选择顶点 $3$,并将其涂为黑色。
  • 在第三轮时,Bob 选择顶点 $4$,并将其涂为黑色。

总共需要 $3$ 轮操作。

对于第二组测试数据,Alice 的一种最优方案为选择顶点 $1$ 将其涂为黑色,此时:

  • 在第一轮时,Bob 选择顶点 $2,3$,并将其涂为黑色。
  • 在第二轮时,Bob 选择顶点 $4$,并将其涂为黑色。

总共需要 $2$ 轮操作。

对于第三组测试数据,Alice 的一种最优方案为选择顶点 $1$ 将其涂为黑色,此时:

  • 在第一轮时,Bob 选择顶点 $2,3$,并将其涂为黑色。
  • 在第二轮时,Bob 选择顶点 $4,5$,并将其涂为黑色。

总共需要 $2$ 轮操作。

子任务

对于所有数据,$2 \le n \le 3 \times 10^5$,$n-1 \le m \le 3 \times 10^5$,$1 \le u_i, v_i \le n$。

对于所有数据,$\sum n \le 3 \times 10^5$,$\sum m \le 3 \times 10^5$。

保证输入的图为简单联通无向图。

子任务编号 $\sum n \le$ $\sum m \le$ 特殊性质 分值
$1$ $16$ $40$ $6$
$2$ $1\,000$ $2\,000$ $10$
$3$ $10^5$ $10^5$ $m=n-1$ $18$
$4$ $m = n$ $13$
$5$ $3 \times 10^5$ $3\times 10^5$ 保证无向图直径为$1$ 到 $n$ $21$
$6$ $32$