CF2122D.Traffic Lights

给定一个包含 $n$ 个顶点 $m$ 条边的简单无向连通图。

初始时刻（第 $0$ 秒时），令牌位于顶点 $1$。设经过 $t$ 秒后令牌位于顶点 $u$，每秒必须选择执行以下操作之一：

• 等待 $1$ 秒；
• 花费 $1$ 秒，让令牌沿顶点 $u$ 的第 $(t\bmod \text{deg}(u)+1)^*$ 条边移动（边的顺序按照输入顺序排列）。

请计算从顶点 $1$ 到顶点 $n$ 的最短总耗时，以及在总耗时最短的前提下能够实现的最小等待时间。

$^{\text{∗}}x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

第一行输入一个整数 $t(1\leq t\leq 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\times 10^5$。

对于每个测试用例，输出一行包括 $2$ 个整数，分别表示最短总耗时，以及在总耗时最短前提下能够实现的最小等待时间。

【样例解释】

第一个测试用例的最优策略如下：

• $0$ 秒时，等待 $1$ 秒；
• $1$ 秒时，将令牌从顶点 $1$ 移动到顶点 $5$；
• $2$ 秒时，等待 $1$ 秒；
• $3$ 秒时，将令牌从顶点 $5$ 移动到顶点 $6$。

第二个测试用例的最优策略如下：

• $0$ 秒时，将令牌从顶点 $1$ 移动到顶点 $2$；
• $1$ 秒时，将令牌从顶点 $2$ 移动到顶点 $1$；
• $2$ 秒时，将令牌从顶点 $1$ 移动到顶点 $4$。