D. Traffic Lights
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a simple undirected connected graph of $$$n$$$ vertices and $$$m$$$ edges.

There is a token in vertex $$$1$$$. We consider the initial time to be at $$$0$$$ seconds. After $$$t$$$ seconds, if the token is in vertex $$$u$$$, you must do exactly one of the following:

  • wait one second,
  • move the token through the $$$(t \bmod \mathrm{deg}(u) + 1)$$$$$$^{\text{∗}}$$$-th edge of $$$u$$$, which takes one second.

The order of edges of a vertex is the order that they appear in the input.

Calculate the minimum time required to move the token from vertex $$$1$$$ to vertex $$$n$$$, and the minimum time spent waiting that can be achieved while minimizing the total time.

$$$^{\text{∗}}$$$$$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

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

Then $$$m$$$ lines follow, the $$$i$$$-th line containing two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — the vertices of the $$$i$$$-th edge.

It is guaranteed that the graph is connected and simple.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output a single line containing two integers — the minimum total time and the minimum waiting time that minimizes the total time, respectively.

Example
Input
2
6 6
1 2
2 3
3 4
4 6
1 5
5 6
4 3
1 2
1 3
1 4
Output
4 2
3 0
Note

In the first test case, an optimal strategy is to do the following:

  • at time $$$0$$$, wait one second,
  • at time $$$1$$$, move the token from vertex $$$1$$$ to vertex $$$5$$$,
  • at time $$$2$$$, wait one second,
  • at time $$$3$$$, move the token from vertex $$$5$$$ to vertex $$$6$$$.

In the second test case, an optimal strategy is to do the following:

  • at time $$$0$$$, move the token from vertex $$$1$$$ to vertex $$$2$$$,
  • at time $$$1$$$, move the token from vertex $$$2$$$ to vertex $$$1$$$,
  • at time $$$2$$$, move the token from vertex $$$1$$$ to vertex $$$4$$$.