题目描述：

在仓库工作的操作员需要使用一台特殊的叉车来移动一个重箱子。仓库可以抽象成 $n$ 个房间，这些房间通过 $m$ 条走廊连接。任何房间都可以通过走廊到达其他房间。房间从 $1$ 到 $n$ 编号。第 $i$ 条走廊直接连接编号为 $u_i$ 和 $v_i$ 的房间，可以双向通过。

叉车可以提起和放下箱子，如果它没有提起箱子，它也可以自由地在房间和走廊之间移动。最初，叉车位于编号为 $1$ 的房间，并且提起了箱子。叉车可以执行以下操作：

1. 如果叉车位于房间 $a$ 并且提起了箱子，它可以在不移动的情况下，将箱子放到与房间 $a$ 通过走廊直接连接的房间 $b$。完成这个操作后，叉车就不再提起箱子，并且可以移动。
2. 如果叉车位于房间 $a$，而箱子放在房间 $b$，并且房间 $a$ 和 $b$ 通过走廊直接连接，叉车可以在不移动的情况下提起箱子。完成这个操作后，叉车仍然位于房间 $a$ 并且提起了箱子，它不能移动，直到将箱子放下。
3. 如果叉车没有提起箱子，它可以在走廊和房间之间移动，但是它不能通过放有箱子的房间。

空叉车在房间之间移动非常快，比提起或放下箱子要快得多。因此，我们认为执行第一个或第二个操作叉车需要花费一单位时间，而第三个操作是瞬间完成的。你的任务是确定对于每个房间 $p$ $(2 \leq p \leq n)$，叉车从在第一个房间提起箱子，到达房间 $p$ 并提起箱子所需的最短时间。或者确定这是不可能的。

输入格式

输入包含多组数据。第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$，表示数据组数。每组数据的格式如下：

每组输入数据的第一行包含两个整数 $n,m$ $(2 \leq n \leq 5\cdot 10^5, 1 \leq m \leq 5\cdot 10^5)$，分别表示仓库中的房间和走廊数量。

接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$ $(1 \leq u_i, v_i \leq n, u_i \neq v_i)$，表示第 $i$ 条走廊连接的房间编号。保证每对房间最多通过一个走廊连接。保证如果所有房间都是空的，可以通过走廊从任何一个房间到达另一个房间。

设 $\sum n$ 为所有输入数据中 $n$ 的总和，$\sum m$ 为所有输入数据中 $m$ 的总和。保证 $\sum n \leq 5\cdot 10^5, \sum m \leq 5\cdot 10^5$。

输出格式

对于每组输入数据，输出 $n - 1$ 个数字：第 $i$ 个数字表示叉车到达第 $i + 1$ 个房间并抬着箱子所需的最少抬起和放下箱子的次数。如果无法到达则输出 $-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$：

1. 将箱子放在房间 $2$。耗时一单位时间。
2. 移动到房间 $3$。耗时为零。
3. 从房间 $2$ 抬起箱子。耗时一单位时间。
4. 将箱子放在房间 $9$。耗时一单位时间。
5. 移动到房间 $6$。耗时为零。
6. 从房间 $9$ 抬起箱子。耗时一单位时间。
7. 将箱子放在房间 $5$。耗时一单位时间。
8. 移动到房间 $4$。耗时为零。
9. 从房间 $5$ 抬起箱子。耗时一单位时间。

总共耗时 $6$ 单位时间。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。