题目描述

雪花图是由两个整数 $x$ 和 $y$（均大于 $1$）生成的，生成方式如下：

• 以一个中心顶点开始。
• 将 $x$ 个新顶点与该中心顶点相连。
• 对每一个这 $x$ 个顶点，各自连接 $y$ 个新顶点。

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

上图中的雪花图有一个中心顶点 $15$，然后有 $x=5$ 个顶点与其相连（$3$、$6$、$7$、$8$ 和 $20$），每个顶点又分别连接 $y=3$ 个顶点。

给定一个雪花图，请你求出 $x$ 和 $y$ 的值。

输入格式

第一行包含一个整数 $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$），表示一条连接顶点 $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$ 之前输出。

由 ChatGPT 4.1 翻译

来源

Codeforces 1829F，英文题名 Forever Winter。