雪花图由两个整数 $$$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$$$ 之前输出。