题目背景

翻译自 ROI 2022 D2T3。

仓库操作员需要使用特殊叉车移动重箱。可以将仓库简化为 $n$ 个房间，通过 $m$ 条走廊连接。可以通过走廊从任意一个房间到达任意其他房间。房间编号从 $1$ 到 $n$。走廊 $i$ 直接连接房间 $u_i$ 和 $v_i$，可以双向移动。

叉车可以升降货物，如果不携带货物，可以在空房间和走廊之间移动。最初，叉车位于房间 $1$，并携带着升起的货物。叉车可以执行以下操作：

1. 如果叉车位于房间 $a$ 并且携带升起的货物，则可以将货物放置在房间 $b$，前提是房间 $a$ 和 $b$ 直接相连。完成此操作后，叉车不再携带货物并可以移动。
2. 如果叉车位于房间 $a$，货物放置在房间 $b$，并且房间 $a$ 和 $b$ 直接相连，则叉车可以在不移动的情况下升起货物。完成此操作后，叉车仍然位于房间 $a$ 并携带升起的货物，直到放下货物之前不能移动。
3. 如果叉车没有携带货物，则可以在走廊和房间之间移动，但不能通过放有货物的房间。

题目描述

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

输入格式

每个测试由多组数据组成。第一行给出一个整数 $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$。

输出格式

对于每组输入，输出 $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

提示

部分样例解释：

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

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

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