CF1903F.Babysitting

Theofanis wants to play video games, however he should also take care of his sister. Since Theofanis is a CS major, he found a way to do both. He will install some cameras in his house in order to make sure his sister is okay.

His house is an undirected graph with $n$ nodes and $m$ edges. His sister likes to play at the edges of the graph, so he has to install a camera to at least one endpoint of every edge of the graph. Theofanis wants to find a vertex cover that maximizes the minimum difference between indices of the chosen nodes.

More formally, let $a_1, a_2, \ldots, a_k$ be a vertex cover of the graph. Let the minimum difference between indices of the chosen nodes be the minimum $\lvert a_i - a_j \rvert$ (where $i \neq j$) out of the nodes that you chose. If $k = 1$ then we assume that the minimum difference between indices of the chosen nodes is $n$.

Can you find the maximum possible minimum difference between indices of the chosen nodes over all vertex covers?

西奥法尼斯想玩电子游戏，但他同时也需要照看他的妹妹。由于西奥法尼斯是计算机科学专业的学生，他找到了一种兼顾二者的方法：他将在家中安装若干摄像头，以确保妹妹的安全。

他的家是一个具有 $n$ 个节点和 $m$ 条边的无向图。他的妹妹喜欢在图的边上玩耍，因此他必须在图的每条边的至少一个端点处安装摄像头。西奥法尼斯希望找到一个顶点覆盖，使得所选节点下标之间的最小差值尽可能大。

更准确地说，设 $a_1, a_2, \ldots, a_k$ 是该图的一个顶点覆盖。所选节点下标之间的最小差值定义为所有所选节点中 $\lvert a_i - a_j \rvert$（其中 $i \neq j$）的最小值。若 $k = 1$（即仅选一个节点），则约定该最小差值为 $n$。

你能否找出在所有顶点覆盖中，所选节点下标之间可能达到的最大最小差值？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^{5}, 1 \le m \le 2 \cdot 10^{5}$) — the number of nodes and the number of edges.

The $i$-th of the following $m$ lines in the test case contains two positive integers $u_i$ and $v_i$ ($1 \le u_i,v_i \le n$), meaning that there exists an edge between them in the graph.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{5}$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^{5}$.

第一行包含一个整数 $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}$。

For each test case, print the maximum minimum difference between indices of the chosen nodes over all vertex covers.

对于每个测试用例，输出所有顶点覆盖中所选节点下标之间最小差值的最大值。

In the first test case, we can install cameras at nodes $1$, $3$, and $7$, so the answer is $2$.

In the second test case, we can install only one camera at node $1$, so the answer is $3$.

在第一个测试用例中，我们可以在节点 $1$、$3$ 和 $7$ 处安装摄像头，因此答案为 $2$。

在第二个测试用例中，我们只能在节点 $1$ 处安装一个摄像头，因此答案为 $3$。