D. Светофоры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан простой неориентированный связный граф из $$$n$$$ вершин и $$$m$$$ рёбер.

Вершина $$$1$$$ содержит фишку. Начальное время считается равным $$$0$$$ секунд. Пусть через $$$t$$$ секунд фишка находится в вершине $$$u$$$, тогда вы должны выполнить одно из следующих действий:

  • подождать одну секунду,
  • переместить фишку по $$$(t \bmod \mathrm{deg}(u) + 1)$$$$$$^{\text{∗}}$$$-му ребру из $$$u$$$, что занимает одну секунду.

Порядок рёбер вершины соответствует порядку, в котором они указаны во входных данных.

Вычислите минимальное время, необходимое для перемещения фишки из вершины $$$1$$$ в вершину $$$n$$$, и минимальное время ожидания, которое можно достичь, минимизируя общее время.

$$$^{\text{∗}}$$$$$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 5000$$$, $$$n - 1 \leq m \leq \frac{n(n - 1)}{2}$$$) — количество вершин и рёбер в графе соответственно.

Затем следуют $$$m$$$ строк, $$$i$$$-я строка содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — вершины $$$i$$$-го ребра.

Гарантируется, что граф связный и простой.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$, а сумма $$$m$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^5$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую два целых числа — минимальное общее время и минимальное время ожидания, которое минимизирует общее время, соответственно.

Пример
Входные данные
2
6 6
1 2
2 3
3 4
4 6
1 5
5 6
4 3
1 2
1 3
1 4
Выходные данные
4 2
3 0
Примечание

В первом наборе входных данных оптимальная стратегия следующая:

  • в момент времени $$$0$$$ подождать одну секунду,
  • в момент времени $$$1$$$ переместить фишку из вершины $$$1$$$ в вершину $$$5$$$,
  • в момент времени $$$2$$$ подождать одну секунду,
  • в момент времени $$$3$$$ переместить фишку из вершины $$$5$$$ в вершину $$$6$$$.

Во втором наборе входных данных оптимальная стратегия следующая:

  • в момент времени $$$0$$$ переместить фишку из вершины $$$1$$$ в вершину $$$2$$$,
  • в момент времени $$$1$$$ переместить фишку из вершины $$$2$$$ в вершину $$$1$$$,
  • в момент времени $$$2$$$ переместить фишку из вершины $$$1$$$ в вершину $$$4$$$.