← 返回题目列表

Codeforces · 1829/F

F. 永远的冬天

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

雪花图由两个整数 $$$x$$$ 和 $$$y$$$ 生成,两者都大于 $$$1$$$,如下所示:

- 从一个中心顶点开始。
- 将 $$$x$$$ 新顶点连接到该中心顶点。
- 将 $$$y$$$ 新顶点连接到每个 $$$x$$$ 顶点。

上面的雪花图有一个中心顶点 $$$15$$$,然后附加到它的 $$$x=5$$$ 顶点($$$3$$$、$$$6$$$、$$$7$$$、$$$8$$$ 和 $$$20$$$),然后附加到每个顶点的 $$$y=3$$$ 顶点。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 200$$$; $$$1 \leq m \leq \min\left(1000, \frac{n(n-1)}{2}\right)$$$) — 分别是图中的顶点数和边数。

接下来的 $$$m$$$ 行每行包含两个整数,每个 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) - 由边连接的顶点数。该图不包含多条边和自环。

对于某些整数 $$$x$$$ 和 $$$y$$$ 都大于 $$$1$$$ 的情况,保证该图是雪花图。

输出

对于每个测试用例,在单独的行上按顺序输出 $$$x$$$ 和 $$$y$$$ 的值,并用空格分隔。

示例

输入 #1

3
21 20
21 20
5 20
13 20
1 3
11 3
10 3
4 8
19 8
14 8
9 7
12 7
17 7
18 6
16 6
2 6
6 15
7 15
8 15
20 15
3 15
7 6
1 2
1 3
2 4
2 5
3 6
3 7
9 8
9 3
3 6
6 2
2 1
5 2
2 7
4 3
3 8

输出 #1

5 3
2 2
2 3

注意

第一个测试用例如声明中所示。请注意,输出 3 5 是不正确的,因为 $$$x$$$ 应该在 $$$y$$$ 之前输出。