Background

Translated from ROI 2022 D2T3.

Problem Description

A warehouse operator needs to use a special forklift to move a heavy box. The warehouse can be simplified as $n$ rooms connected by $m$ corridors. You can travel from any room to any other room using the corridors. The rooms are numbered from $1$ to $n$. Corridor $i$ directly connects rooms $u_i$ and $v_i$, and it can be used in both directions.

The forklift can lift and lower the cargo. If it is not carrying the cargo, it can move between rooms and corridors. Initially, the forklift is in room $1$ and is carrying the cargo in the lifted state. The forklift can perform the following actions:

1. If the forklift is in room $a$ and is carrying the lifted cargo, it can place the cargo into room $b$, provided that rooms $a$ and $b$ are directly connected. After this action, the forklift is no longer carrying the cargo and can move.
2. If the forklift is in room $a$, the cargo is placed in room $b$, and rooms $a$ and $b$ are directly connected, then the forklift can lift the cargo without moving. After this action, the forklift remains in room $a$ and carries the lifted cargo, and it cannot move until it places the cargo down.
3. If the forklift is not carrying the cargo, it can move through corridors between rooms, but it cannot pass through a room that contains the cargo.

Moving an empty forklift between rooms is very fast, much faster than lifting or lowering the cargo. Therefore, we assume that performing action 1 or action 2 takes one unit of time, while action 3 is instantaneous. For each room $p(2 \le p \le n)$, determine the shortest time needed for the forklift to go from the initial state (in room $1$ and carrying the lifted cargo) to room $p$ and still be carrying the lifted cargo, or determine that this is impossible.

Input Format

Each input contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 100,000$), the number of test cases. The description of each test case follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 500,000, 1 \le m \le 500,000$), the numbers of rooms and corridors in the warehouse.

The next $m$ lines each contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \ne v_i$), meaning that the $i$-th corridor connects these two rooms. It is guaranteed that each unordered pair of rooms connected by a corridor appears at most once (i.e., each corridor is given only once). It is guaranteed that if all rooms are empty, then you can reach any room from any other room using the corridors, i.e., the graph is connected.

Let $\sum n$ be the sum of $n$ over all test cases, and $\sum m$ be the sum of $m$ over all test cases. It is guaranteed that $\sum n \le 500,000$ and $\sum m \le 500,000$.

Output Format

For each test case, output $n - 1$ numbers. The $i$-th number should be the minimum number of lift/lower operations (i.e., the shortest time) needed for the forklift to start from room $1$ and reach room $i+1$ (while still carrying the lifted cargo). If it is impossible, the $i$-th number should be $-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

Explanation for part of the samples:

In the fourth test case, to make the forklift go from room $1$ (carrying the lifted cargo) to room $4$ as fast as possible (and still carry the lifted cargo), it can perform the following actions:

• Place the cargo into room $2$. This takes one unit of time.
• Move to room $3$. This takes no time.
• Lift the cargo from room $2$. This takes one unit of time.
• Place the cargo into room $9$. This takes one unit of time.
• Move to room $6$. This takes no time.
• Lift the cargo from room $9$. This takes one unit of time.
• Place the cargo into room $5$. This takes one unit of time.
• Move to room $4$. This takes no time.
• Lift the cargo from room $5$. This takes one unit of time.

In total, it takes $6$ units of time.

Translated by ChatGPT 5