题目描述

雪花图是由两个大于 $1$ 的整数 $x$ 和 $y$ 生成的，具体如下：

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

例如，下面是一个 $x=5$ 和 $y=3$ 的雪花图。

在上面的雪花图中，中心顶点是 15，然后连接到它的有 $x=5$ 个顶点（3、6、7、8 和 20），然后每个这些 $x$ 个顶点又连接到 $y=3$ 个顶点。

给定一个雪花图，确定 $x$ 和 $y$ 的值。

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $m(2≤n≤200；1≤m≤min(1000,\frac{n(n−1)}2))$ ——图中的顶点和边的数量。

接下来的m行每行包含两个整数 $u$ 和 $v(1≤u,v≤n，u≠v)$ ——由一条边连接的顶点编号。图中不存在多重边和自环。

保证此图是某些大于 $1$ 的整数 $x$ 和 $y$ 的雪花图。

输出格式

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

测试样例

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

5 3
2 2
2 3

样例说明

第一个测试案例在陈述中有图示。请注意，输出 3 5 是错误的，因为应该先输出 $x$，然后是 $y$。