You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Timi没见过下雪，也没见过雪花，因此他非常想了解雪花的形状。

雪花的形状如下所示：

• 有一个中心顶点。
• 有$x(x>1)$个新顶点连接到这个中心顶点。
• 对于$x$个新顶点，每个顶点又有$y(y>1)$个新顶点与其连接。

例如，$x=5$和$y=3$的雪花形状如图所示：

上图中的雪花形状有一个中心顶点$15$，将$x=5$个顶点连接到它上面（$3$、$6$、$7$、$8$和$20$），对于这$x=5$个新顶点，每个顶点又有$y=3$个新顶点与其连接。

现在Timi知道一个雪花形状，请你帮他确定$x$和$y$的值。

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含两个正整数$n$和$m$，表示雪花形状的顶点数和边数。

每个测试用例接下来有$m$行，每行包含两个整数$u$和$v$，表示一条边上的两个顶点，即这两个点之间有一条边。

保证输入数据是某个$x>1$和$y>1$的雪花形状图。

输出格式

对于每个测试用例，输出两个正整数$x$和$y$，$x$和$y$用一个空格隔开。

2
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

5 3
2 2

提示

【样例解释】

第一个测试用例在题面中已经给出。请注意，如果输出3 5是错误的，因为在输出时应该先输出$x$再输出$y$。

【数据范围】

对于所有数据，保证$1\leq t\leq1000,2\leq n,m\leq 200,1\leq u,v\leq n,u\neq v$。