무거운 화물

창고 운영자가 특수 지게차로 무거운 상자를 옮겨야 한다. 창고는 $m$개의 복도로 연결된 $n$개의 방으로 나타낼 수 있다. 어떤 방에서든 복도를 따라가면 다른 모든 방에 도달할 수 있다. 방은 1부터 $n$까지 번호가 매겨져 있다. $i$번째 복도는 방 $u_i$와 방 $v_i$를 직접 연결하며, 양방향으로 지나갈 수 있다.

지게차는 상자를 들어 올리거나 내려놓을 수 있다. 상자를 들고 있지 않을 때는 빈 방과 복도를 따라 이동할 수 있다. 처음에 지게차는 1번 방에 있고 상자를 들고 있다. 지게차가 할 수 있는 행동은 다음과 같다.

1. 지게차가 방 $a$에 있고 상자를 들고 있으면, 방 $a$와 방 $b$가 복도로 직접 연결되어 있을 때 움직이지 않고 상자를 방 $b$에 내려놓을 수 있다. 이 행동 후에는 상자를 들고 있지 않으므로 이동할 수 있다.
2. 지게차가 방 $a$에 있고 상자가 방 $b$에 놓여 있으면, 방 $a$와 방 $b$가 복도로 직접 연결되어 있을 때 움직이지 않고 상자를 들어 올릴 수 있다. 이 행동 후 지게차는 방 $a$에 머무르며 상자를 들고 있고, 상자를 내려놓기 전까지는 이동할 수 없다.
3. 지게차가 상자를 들고 있지 않으면 복도와 방을 따라 이동할 수 있다. 다만 상자가 놓여 있는 방은 지나갈 수 없다.

빈 지게차는 상자를 들어 올리거나 내리는 것보다 훨씬 빠르게 움직인다. 그래서 행동 1과 행동 2는 각각 단위 시간 1이 걸리고, 행동 3은 시간이 걸리지 않는다. 각 방 $p$($2 \le p \le n$)에 대해, 처음 상태(1번 방에서 상자를 들고 있는 상태)에서 상자를 든 채로 방 $p$에 도달하는 데 걸리는 최소 시간을 구하라. 도달할 수 없는 경우도 있으며, 그때는 그 사실을 보고해야 한다.

여러 개의 입력 데이터로 이루어진 테스트이다. 첫 줄에는 입력 데이터의 개수 $t$($1 \le t \le 100000$)가 주어진다. 그다음에 각 입력 데이터가 이어진다.

각 입력 데이터의 첫 줄에는 방의 개수 $n$과 복도의 개수 $m$이 주어진다($2 \le n \le 500000$, $1 \le m \le 500000$).

다음 $m$개의 줄에는 $i$번째 복도가 연결하는 두 방의 번호 $u_i$, $v_i$가 주어진다($1 \le u_i, v_i \le n$, $u_i \ne v_i$). 복도로 직접 연결된 방의 쌍은 정확히 한 번씩만 주어진다. 모든 방이 비어 있을 때 어떤 방에서든 복도를 따라 다른 모든 방에 도달할 수 있음이 보장된다.

모든 입력 데이터의 $n$ 합은 500000 이하이고, $m$ 합은 500000 이하이다.

각 입력 데이터에 대해 $n - 1$개의 수를 출력한다. $i$번째 수는 상자를 든 채로 방 $i + 1$에 도달하기 위해 필요한 상자의 최소 들어 올리기 및 내려놓기 횟수이다. 도달할 수 없으면 $i$번째 수는 $-1$이다.

네 번째 입력 데이터에서 지게차는 다음 순서로 움직이면 1번 방에서 상자를 든 채로 4번 방에 가장 빨리 도착할 수 있다.

• 상자를 2번 방에 내려놓는다. 1단위 시간이 걸린다.
• 3번 방으로 이동한다. 시간이 걸리지 않는다.
• 2번 방에서 상자를 들어 올린다. 1단위 시간이 걸린다.
• 상자를 9번 방에 내려놓는다. 1단위 시간이 걸린다.
• 6번 방으로 이동한다. 시간이 걸리지 않는다.
• 9번 방에서 상자를 들어 올린다. 1단위 시간이 걸린다.
• 상자를 5번 방에 내려놓는다. 1단위 시간이 걸린다.
• 4번 방으로 이동한다. 시간이 걸리지 않는다.
• 5번 방에서 상자를 들어 올린다. 1단위 시간이 걸린다.

총 6단위 시간이 소요된다.