CF1903F Babysitting

Theofanis 想玩电子游戏，但他还需要照顾他的妹妹。由于 Theofanis 是计算机专业的学生，他想到了两全其美的办法。他打算在家里安装一些摄像头，以确保妹妹的安全。 他的家可以用一个无向图表示，图中有 $n$ 个节点和 $m$ 条边。他的妹妹喜欢在图的边上玩耍，因此他必须在每条边的至少一个端点安装摄像头。Theofanis 想要找到一个顶点覆盖，使得所选节点编号之间的最小差值最大。 更正式地说，设 $a_1, a_2, \ldots, a_k$ 是图的一个顶点覆盖。所选节点编号之间的最小差值定义为所有 $|a_i - a_j|$（其中 $i \neq j$）的最小值。如果 $k = 1$，则认为所选节点编号之间的最小差值为 $n$。 你能否找到所有顶点覆盖中，节点编号最小差值的最大值？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^{5}, 1 \le m \le 2 \cdot 10^{5}$），分别表示节点数和边数。 接下来的 $m$ 行中，第 $i$ 行包含两个正整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示在 $u_i$ 和 $v_i$ 之间有一条边。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示所有顶点覆盖中节点编号最小差值的最大值。

在第一个测试用例中，可以在节点 $1$、$3$ 和 $7$ 处安装摄像头，因此答案为 $2$。  在第二个测试用例中，只需在节点 $1$ 处安装一个摄像头，因此答案为 $3$。 由 ChatGPT 4.1 翻译