← 返回题目列表

Codeforces · 2122/D

D. 交通灯

中文机器翻译题面 查看原题

给你一个简单的无向连通图,其中有 $$$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$$$。