伯兰有 $$$n$$$ 个城市。编号为$$$1$$$的城市是首都。一些城市对通过长度为 1 的单向道路连接。
在出行之前,Polycarp 为每个城市找出了 $$$d_i$$$ 的值——从首都(第 $$$1$$$ 个城市)到第 $$$i$$$ 个城市的最短距离。
坡旅甲在编号为 $$$s$$$ 的城市开始他的旅程,并且在第 $$$i$$$ 个城市中,选择以下操作之一:
1. 如果存在从第 $$$i$$$-th 城市到第 $$$j$$$-th 的道路且 $$$d_i < d_j$$$,则从第 $$$i$$$-th 城市前往第 $$$j$$$-th 城市;
2. 如果存在从第 $$$i$$$-th 城市到第 $$$j$$$-th 的道路且 $$$d_i \geq d_j$$$,则从第 $$$i$$$-th 城市前往第 $$$j$$$-th 城市;
3. 停止行驶。
由于贝兰德政府不希望所有人都来到首都,因此波利卡普最多只能执行一次列表中的第二个行动。换句话说,他可以在旅途中执行第二个动作 $$$0$$$ 或 $$$1$$$ 时间。另一方面,波利卡普则希望尽可能靠近首都。
例如,如果 $$$n = 6$$$ 并且城市是相连的,如上图所示,那么坡旅甲可以进行以下旅行(并非所有可能的选择):
- $$$2 \rightarrow 5 \rightarrow 1 \rightarrow 2 \rightarrow 5$$$;
- $$$3 \rightarrow 6 \rightarrow 2$$$;
- $$$1 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 5$$$。
Polycarp 希望每个起始城市 $$$i$$$ 找出他距离首都有多近。更正式地说:他想要根据上述规则找到 Polycarp 从城市 $$$i$$$ 到城市 $$$j$$$ 可以得到的 $$$d_j$$$ 的最小值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例前面都有一个空行。
每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) 和 $$$m$$$ ($$$1 \leq m \leq 2 \cdot 10^5$$$) - 分别是城市和道路的数量。
接下来是描述道路的 $$$m$$$ 行。每条道路都由两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n, u \ne v$$$) 来表征 - 由单向道路连接的城市数量。
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
保证对于每对不同的城市 $$$(u, v)$$$ 至多有一条从 $$$u$$$ 到 $$$v$$$ 的道路(但是从 $$$u$$$ 到 $$$v$$$ 和从 $$$v$$$ 到 $$$u$$$ 的一对道路是有效的)。
保证从首都到所有城市都有路径。
输出
对于每个测试用例,在单独的行上输出 $$$n$$$ 数字,其中第 $$$i$$$ 等于从首都到波利卡普结束旅程的城市的最小可能距离。
示例
输入 #1
3 6 7 1 2 1 3 2 5 2 4 5 1 3 6 6 2 2 2 1 2 2 1 6 8 1 2 1 5 2 6 6 1 2 3 3 4 4 2 5 4
输出 #1
0 0 1 2 0 1 0 0 0 0 2 1 1 0