Heavy Cargo

Warehouse operators need to move a heavy box with a special forklift. The warehouse can be modeled as $n$ rooms connected by $m$ corridors. From any room, you can reach any other room by walking through corridors. The rooms are numbered from 1 to $n$. Corridor $i$ directly connects rooms $u_i$ and $v_i$, and it can be traversed in both directions.

The forklift can lift and put down the box. When it is not holding the box, it can move through free rooms and corridors. At the start, the forklift is in room 1 and holds the box. The forklift supports these actions:

1. If the forklift is in room $a$ and holds the box, it can put the box down in room $b$ without moving, provided rooms $a$ and $b$ are directly connected by a corridor. After this action, the forklift no longer holds the box and can move.
2. If the forklift is in room $a$ and the box is in room $b$, it can pick up the box without moving, provided rooms $a$ and $b$ are directly connected by a corridor. After this action, the forklift stays in room $a$ and holds the box. It cannot move until it puts the box down.
3. If the forklift is not holding the box, it can move through corridors and rooms. It cannot pass through a room where the box lies.

An empty forklift moves much faster than it lifts or lowers the box. So action 1 or action 2 takes one unit of time, and action 3 takes no time. For each room $p$ ($2 \le p \le n$), find the minimum time the forklift needs to go from the start state (room 1, holding the box) to room $p$ while holding the box. If that is impossible, report it.

Each test consists of several input sets. The first line contains one integer $t$ ($1 \le t \le 100000$), the number of input sets. Then the input sets follow.

The first line of each input set contains two integers $n$ and $m$ ($2 \le n \le 500000$, $1 \le m \le 500000$), the number of rooms and corridors.

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$), the numbers of the rooms connected by the $i$-th corridor. Each pair of rooms connected by a corridor is listed exactly once. It is guaranteed that if all rooms are empty, you can reach any room from any other room by walking through corridors.

Let the sum of $n$ over all input sets be at most 500000, and the sum of $m$ be at most 500000.

For each input set, print $n - 1$ numbers. The $i$-th number is the minimum number of lifts and put-downs of the box needed for the forklift to reach room $i + 1$ while holding the box. If it is impossible, the $i$-th number is $-1$.

In the fourth input set, the forklift can reach room 4 holding the box in the fastest way as follows:

• Put the box down in room 2. This takes one unit of time.
• Move to room 3. This takes no time.
• Pick up the box from room 2. This takes one unit of time.
• Put the box down in room 9. This takes one unit of time.
• Move to room 6. This takes no time.
• Pick up the box from room 9. This takes one unit of time.
• Put the box down in room 5. This takes one unit of time.
• Move to room 4. This takes no time.
• Pick up the box from room 5. This takes one unit of time.

In total, 6 units of time are spent.