Forklift Delivery Time

In a building with n rooms and m corridors connecting some pairs of rooms, a forklift starts in room 1 carrying cargo in the raised position. Because an empty forklift moves very fast between rooms compared to the time it takes to lift or lower cargo, we assume that the forklift takes 1 unit of time to perform either the cargo lowering or the moving operation, while the cargo lifting operation is instantaneous.

In order for the forklift to travel from a room with raised cargo to an adjacent room and finish with the cargo raised, it must execute the following steps:

• Lower the cargo in the current room (1 time unit).
• Move empty to an adjacent room (1 time unit).
• Lift the cargo in the new room (0 time units).

Thus, moving along any corridor effectively costs 2 time units. Given that the forklift starts at room 1 (with raised cargo), determine for each room p (2 ≤ p ≤ n) the minimum time needed to reach room p with the cargo in the raised position, or determine that it is impossible.

Note: The corridors are bidirectional and there is at most one corridor between any two rooms.

inputFormat

The first line contains two integers n and m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵), representing the number of rooms and corridors respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), which describe a corridor connecting room u and room v.

outputFormat

Output n - 1 lines. For each room p (from 2 to n), output the minimum time required for the forklift to reach room p with its cargo raised. If a room is unreachable, output -1 instead.

sample

4 3
1 2
2 3
3 4

2
4
6