310412: CF1829F. Forever Winter

F. Forever Wintertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.Input

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$.

Output

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

ExampleInput

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

Output

5 3
2 2
2 3

Note

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

题目大意：
一个雪花图是由两个大于1的整数x和y生成的，生成方式如下：
1. 从一个中心顶点开始。
2. 将x个新顶点连接到这个中心顶点。
3. 将y个新顶点连接到这x个顶点中的每一个。

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

输入数据格式：
第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
每个测试用例的第一行包含两个整数n和m（2≤n≤200；1≤m≤min(1000, 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题目大意： 一个雪花图是由两个大于1的整数x和y生成的，生成方式如下： 1. 从一个中心顶点开始。 2. 将x个新顶点连接到这个中心顶点。 3. 将y个新顶点连接到这x个顶点中的每一个。 给定一个雪花图，确定x和y的值。 输入数据格式： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例的第一行包含两个整数n和m（2≤n≤200；1≤m≤min(1000, 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