Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Вечная зима
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Граф-снежинка генерируется из двух целых чисел $$$x$$$ и $$$y$$$, которые больше $$$1$$$, следующим образом:

  • Начните с одной центральной вершины.
  • Подключите $$$x$$$ новых вершин к этой центральной вершине.
  • Подключите $$$y$$$ новых вершин к каждой из этих $$$x$$$ вершин.
Например, ниже приведен граф-снежинка для $$$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$$$) — номера вершин, соединенных ребром. Граф не содержит кратных ребер и петель.

Гарантируется, что этот граф является графом снежинки для некоторых целых чисел $$$x$$$ и $$$y$$$, которые больше $$$1$$$.

Выходные данные

Для каждого набора входных данных на отдельной строке выведите значения $$$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$$$.