题目描述

2026 丙午马年，某快递公司运营着一张覆盖全国的物流网络，快递员马不停蹄地在各驿站之间接力配送。

该网络共设有 \(n\) 座驿站，编号为 \(1, 2, \ldots, n\)，驿站之间由 \(m\) 条单向运输线路相连。每座驿站的编号代表其安全等级——编号越大，途经该驿站包裹丢失的风险越高。

一条从驿站 \(1\) （总部）到驿站 \(i\) 的运输路线 \(P = (v_1, v_2, \ldots, v_k)\) （其中 \(v_1 = 1, \ v_k = i\)）的风险值定义为途经所有驿站编号的最大值，即：

\[ \text{risk}(P) = \max_{1 \le j \le k} v_j \]

调度员需要为每座驿站规划最安全的配送路线。对于每个驿站 \(i \in \{1, 2, \ldots, n\}\)，求从总部出发到达驿站 \(i\) 的所有路线中风险值的最小值。若驿站 \(i\) 无法从总部到达，输出 \(-1\)。

输入格式

本题有多组测试数据。输入 \(T\ (1 \le T \le 10^3)\)，表示数据组数。

对于每组数据（相邻两组数据间用一空行隔开）：

第一行输入两个正整数 \(n, m\ (1 \le n \le 10^5, \ 1 \le m \le 2 \times 10^5)\)。

接下来 \(m\) 行，每行输入两个正整数 \(u, v\ (1 \le u, v \le n)\)，表示一条从驿站 \(u\) 到驿站 \(v\) 的单向驿道。图中可能存在重边和自环。

保证所有数据的 \(n\) 的和不超过 \(10^6\)， \(m\) 的和不超过 \(2 \times 10^6\)。

输出格式

对于每组数据：

输出一行 \(n\) 个整数，第 \(i\) 个整数表示从总部到驿站 \(i\) 的最小风险值。若不可达，输出 \(-1\)。

样例输入

3
5 4
1 2
1 3
4 5
5 4

4 4
1 4
4 3
2 3
3 2

6 5
1 3
3 2
1 4
4 5
5 2

样例输出

1 2 3 -1 -1
1 4 4 4
1 3 3 4 5 -1