给你一个简单的无向连通图,其中有 $$$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$$$。
输出
对于每个测试用例,输出一行包含两个整数 - 分别是最小总时间和最小化总时间的最小等待时间。
示例
输入复制
26 61 22 33 44 61 55 64 31 21 31 4
输出复制
4 2 3 0
注意
在第一个测试用例中,最佳策略是执行以下操作:
- 时间 $$$0$$$,请等待一秒钟,
- 在时间$$$1$$$,将令牌从顶点$$$1$$$移动到顶点$$$5$$$,
- 时间 $$$2$$$,请等待一秒钟,
- 在时间 $$$3$$$,将令牌从顶点 $$$5$$$ 移动到顶点 $$$6$$$。
在第二个测试用例中,最佳策略是执行以下操作:
- 在时间$$$0$$$,将令牌从顶点$$$1$$$移动到顶点$$$2$$$,
- 在时间$$$1$$$,将令牌从顶点$$$2$$$移动到顶点$$$1$$$,
- 在时间 $$$2$$$,将令牌从顶点 $$$1$$$ 移动到顶点 $$$4$$$。