题意简述
给你一个由 $n$ 个顶点和 $m$ 条边组成的简单无向连通图。
顶点 $1$ 有一个令牌。我们认为初始时间为 $0$ 秒。在 $t$ 秒之后，如果令牌位于顶点 $u$ ，则必须执行以下操作之一：
- 等待一秒。
- 将令牌移动通过 $u$ 的第 $(t \bmod \mathrm{deg}(u) + 1)$ 条边，这需要一秒钟。
顶点的边的顺序就是它们在输入中出现的顺序。
计算将令牌从顶点 $1$ 移到顶点 $n$ 所需的最短时间，以及在总时间最小化的情况下所需的最短等待时间。
$^{\text{∗}}$ $x \bmod y$ 表示用 $x$ 除以 $y$ 所得的余数。
思路分析
没卡在思路上。卡在实现上了。好吧其实也不应该卡在实现上。
记 $f(t,i)$ 表示第 $t$ 秒位于点 $i$ 的最少等待时间。
有转移 $f(t+1,i)=f(t,i)+1$ 和 $f(k,i)=f(t,i)$，其中 $k$ 表示 $t$ 时刻从点 $i$ 可转移到的点。
这题其实就完事了。从小到大枚举 $t$ 即可。