Description

空车在房间之间移动非常快，比升降货物的速度快得多。因此，我们假设叉车执行第一或第二操作需要一单位时间，而第三个操作是瞬时完成的。对于每个房间 $p(2 \le p \le n)$，需要确定叉车从初始位置（在第一个房间且携带升起的货物）到达房间 $p$ 并继续携带升起的货物所需的最短时间，或者确定这是不可能的。

Input Format

每个测试由多组数据组成。第一行给出一个整数 $t$（$1 \le t \le 100,000$），即数据的组数。接下来是每组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500,000,1 \le m \le 500,000$），即仓库中房间和走廊的数量。

接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n,u_i \ne v_i$），表示第 $i$ 条走廊连接的两个房间编号。保证每对通过走廊连接的房间只会出现一次（或者说每个走廊只输入一次）。保证如果所有房间都是空闲的，则可以通过走廊从任意房间到达任意其他房间，即由仓库简化成的图是联通的。

用 $\sum n$ 表示每一组数据中 $n$ 的总和，用 $\sum m$ 表示 $m$ 的总和，保证 $\sum n \le 500,000,\sum m \le 500,000$。

Output Format

对于每组输入，输出 $n - 1$ 个数字，其中第 $i$ 个数字应该等于叉车从房间 $1$ 开始到房间 $i+1$（同时继续携带升起的货物）需要升降货物的最小次数（也就是最短时间）。如果无法实现，则第 $i$ 个数字应为 $-1$。

4
4 4
1 2
2 3
3 4
4 1
5 5
1 2
2 3
3 4
4 5
5 1
5 6
1 2
3 2
1 3
3 5
5 4
3 4
9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
3 6
6 9
9 3

-1 2 -1
4 2 2 4
2 2 4 4
2 2 6 6 4 6 6 4

Hint

部分样例解释：

在第四组数据中，为了使叉车从房间 $1$ 开始（携带升起的货物）尽快到达房间 $4$（并继续携带升起的货物），可以执行以下操作：

• 将货物放置在房间 $2$。需要花费一单位时间。
• 移动到房间 $3$。不需要花费时间。
• 从房间 $2$ 中升起货物。需要花费一单位时间。
• 将货物放置在房间 $9$。需要花费一单位时间。
• 移动到房间 $6$。不需要花费时间。
• 从房间 $9$ 中升起货物。需要花费一单位时间。
• 将货物放置在房间 $5$。需要花费一单位时间。
• 移动到房间 $4$。不需要花费时间。
• 从房间 $5$ 中升起货物。需要花费一单位时间。

总共需要花费 $6$ 个单位时间。