← 返回题目列表

Codeforces · 1903/F

F. 保姆

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

Theofanis 想要玩电子游戏,但他也应该照顾他的妹妹。由于 Theofanis 是计算机科学专业的学生,​​因此他找到了一种可以同时实现这两点的方法。他会在家里安装一些摄像头,以确保妹妹平安无事。

他的房子是一个无向图,有 $$$n$$$ 节点和 $$$m$$$ 边。他的妹妹喜欢在图的边缘玩耍,所以他必须在图的每条边的至少一个端点上安装一台摄像头。 Theofanis 希望找到一个顶点覆盖,使所选节点的索引之间的最小差异最大化。

更正式地说,令 $$$a_1, a_2, \ldots, a_k$$$ 为图的顶点覆盖。令所选节点索引之间的最小差异为您选择的节点中的最小值 $$$\lvert a_i - a_j \rvert$$$ (其中 $$$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$$$),这意味着图中它们之间存在边。

保证所有测试用例的$$$n$$$总和不超过$$$10^{5}$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印所有顶点覆盖上所选节点的索引之间的最大最小差异。

示例

输入 #1

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

输出 #1

2
3
2

注意

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

在第二个测试用例中,我们只能在节点$$$1$$$处安装一台摄像头,所以答案是$$$3$$$。