该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

小 $\alpha$ 遇到了传说中的智者，为了检验小 $\alpha$ 的能力，智者将让小 $\alpha$ 玩一个游戏。

智者将给出一个 $n$ 个点 $m$ 条边的简单连通无向图 $G$，初始时图 $G$ 中将恰有一个节点为红色，其余节点均为蓝色。小 $\alpha$ 将按照如下方式进行若干轮操作，直到图 $G$ 中的所有节点均被染成红色，即完成了智者的游戏：

• 小 $\alpha$ 选择一个大小为 $1$ 或 $2$ 的节点集合 $S$，满足 $S$ 中的点均为蓝色，且对于每一个 $S$ 中的每一个节点 $x$，在图 $G$ 中至少有一个红色节点与 $x$ 相邻。
• 小 $\alpha$ 将 $S$ 中的节点染成红色。

现在智者还没有告诉他图 $G$ 中究竟哪一个节点是红色的，所以小 $\alpha$ 想要知道，对于图 $G$ 中的每一个节点 $x$，如果令 $F(x)$ 表示若初始时图 $G$ 中红色的节点为 $x$，小 $\alpha$ 最少需要多少轮操作才能完成智者的游戏，那么 $\max_{i=1}^{n}F(i)$ 的值是多少呢？精通程序设计的你能帮助他完成这个问题的求解吗？

【输入格式】

从文件 game.in 中读入数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。特别的，样例的 $c$ 表示该样例与编号为 $c$ 的测试点的约束条件相同。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 $n,m$，表示智者给出的图 $G$ 的点数与边数；
• 接下来 $m$ 行，第 $i$ 行包含两个正整数 $u_i,v_i$，表示图 $G$ 有一条连接 $u_i,v_i$ 的无向边。

【输出格式】

输出到文件 game.out 中。

对于每组数据，输出一行一个整数，表示每组数据中 $\max_{i=1}^{n}F(i)$ 的值。

【样例输入1】

1 1
5 7
5 4
4 1
1 3
3 2
3 4
3 5
4 2

【样例输出1】

2

【样例解释1】

对于给定的图 $G$，可以证明初始时图 $G$ 中红色的节点为任意节点，最少需要操作的轮数均为 $2$，因此 $\max_{i=1}^{n}F(i)=2$。

【样例输入/输出2】

见选手目录下的 game2.in/ans，该样例满足测试点 $1$ 的限制。

【样例输入/输出3】

见选手目录下的 game3.in/ans，该样例满足测试点 $3$ 的限制。

【样例输入/输出4】

见选手目录下的 game4.in/ans，该样例满足测试点 $7$ 的限制。

【样例输入/输出5】

见选手目录下的 game5.in/ans，该样例满足测试点 $11$ 的限制。

【样例输入/输出6】

见选手目录下的 game6.in/ans，该样例满足测试点 $16$ 的限制。

【样例输入/输出7】

见选手目录下的 game7.in/ans，该样例满足测试点 $19$ 的限制。

【数据范围】

对于所有测试数据，保证：

• $1\leq T\leq 10$；
• $2\leq n\leq 10^5,n-1\leq m\leq 2\times 10^5$；
• 对于所有 $1\leq i\leq m$，满足 $1\leq u_i,v_i\leq n$；
• 保证输入的图 $G$ 为简单连通无向图。

每个测试点的具体限制如下表：

特殊性质 A：$m=n-1$。

特殊性质 B：$m=n$。

特殊性质 C：保证对于所有 $1\leq i\leq n$，$(i,i+1)$ 为 $G$ 的一条边。

samples