CF1829F.Forever Winter

A snowflake graph is generated from two integers $x$ and $y$, both greater than $1$, as follows:

• Start with one central vertex.
• Connect $x$ new vertices to this central vertex.
• Connect $y$ new vertices to each of these $x$ vertices.

For example, below is a snowflake graph for $x=5$ and $y=3$.

The snowflake graph above has a central vertex $15$, then $x=5$ vertices attached to it ($3$, $6$, $7$, $8$, and $20$), and then $y=3$ vertices attached to each of those.

Given a snowflake graph, determine the values of $x$ and $y$.

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

• 从一个中心顶点开始；
• 将 $x$ 个新顶点连接到该中心顶点；
• 再将 $y$ 个新顶点分别连接到上述 $x$ 个顶点中的每一个。

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

上图所示的雪花图中，中心顶点为 $15$，与之相连的 $x=5$ 个顶点为 $3$、$6$、$7$、$8$ 和 $20$，而每个这样的顶点又各自连接着 $y=3$ 个顶点。

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

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 200$; $1 \leq m \leq \min\left(1000, \frac{n(n-1)}{2}\right)$) — the number of vertices and edges in the graph, respectively.

The next $m$ lines each contain two integers each $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$) — the numbers of vertices connected by an edge. The graph does not contain multiple edges and self-loops.

It is guaranteed that this graph is a snowflake graph for some integers $x$ and $y$ both greater than $1$.

第一行包含一个整数 $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$）—— 表示由一条边连接的两个顶点的编号。该图不含重边和自环。

保证该图对某个大于 $1$ 的整数 $x$ 和 $y$ 构成一个雪花图（snowflake graph）。

For each test case, on a separate line output the values of $x$ and $y$, in that order, separated by a space.

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

The first test case is pictured in the statement. Note that the output 3 5 is incorrect, since $x$ should be output before $y$.

第一个测试用例如题面图示所示。注意，输出 3 5 是错误的，因为 $x$ 应当在 $y$ 之前输出。