D. 交通灯
时间限制：2 秒
内存限制：256 兆字节

你有一个由 $n$ 个顶点和 $m$ 条边组成的简单无向连通图。

在顶点 $1$ 上有一个标记。我们设初始时间为 $0$ 秒。
经过 $t$ 秒后，如果标记位于顶点 $u$，你必须且只能执行以下操作之一：

• 等待一秒，
• 通过顶点 $u$ 的第 $(t \bmod \deg(u) + 1)$ 条边移动标记，耗时一秒。

顶点 $u$ 的边顺序按输入中的出现顺序确定。

计算将标记从顶点 $1$ 移动到顶点 $n$ 所需的最短总时间，以及在总时间最短的前提下能达到的最短等待时间。

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 1000$）。
每个测试用例的描述如下：

第一行包含两个整数 $n, m$（$2 \le n \le 5000$，$n-1 \le m \le \frac{n(n-1)}{2}$）—— 图的顶点数和边数。

接下来 $m$ 行，第 $i$ 行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le 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$。