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.

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