BOJ 27180 Тяжелый груз

문제 링크:

문제 내용

당신은 어떤 창고에서 특별한 리프트를 이용해서 거대한 상자를 옮기려고 합니다. 이 창고는 $n$개의 방과 $m$개의 복도로 이루어져 있으며, 각 방에는 1부터 $n$까지의 서로 다른 번호가 붙어 있습니다. 각각의 복도는 서로 다른 두 방을 연결하며, 모든 복도를 통해서 양방향으로 이동할 수 있습니다.

거대한 상자는 처음에 1번 방에 있으며, 리프트 위에 올려져 있습니다. 당신은 상자를 옮기기 위해 다음과 같은 행동을 할 수 있습니다.

• $i$번 방에서 리프트 위에 상자가 올려져 있을 때, $i$번 방에서 하나의 복도로 연결된 $j$번 방에 상자를 내려놓을 수 있습니다. 리프트는 $i$번 방에 그대로 있습니다. 이 행동의 비용은 1입니다.
• $i$번 방에 상자가 놓여 있고 $i$번 방에서 하나의 복도로 연결된 $j$번 방에 리프트가 있을 때, 상자를 들어올릴 수 있습니다. 리프트와 상자는 $j$번 방에 있게 됩니다. 이 행동의 비용은 1입니다.
• $i$번 방에 상자가 놓여 있고 $j$($i \neq j$)번 방에 리프트가 있을 때, $j$번 방에서 하나의 복도로 연결된 $k$번 방으로 리프트를 이동할 수 있습니다. $k$번 방에 상자가 있다면 이동할 수 없습니다. 이 행동의 비용은 0입니다.

1번 방을 제외한 $2, 3, \cdots, n$번 방에 리프트 위에 상자가 올려져 있도록 하기 위해 필요한 최소 비용을 구하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 100\;000$)

각 테스트 케이스에 대해, 첫 번째 줄에 $n$과 $m$이 주어집니다. ($2 \le n \le 500\;000$, $1 \le m \le 500\;000$)

다음 $m$줄에 걸쳐서 $i$번째 줄에는 $i$번째 복도가 잇는 두 방의 번호 $u_i$와 $v_i$가 주어집니다. ($1 \le u_i, v_i \le n$, $u_i \neq v_i$)

주어지는 그래프는 단순 연결 그래프이며, $n$와 $m$의 총합은 각각 $500\;000$을 초과하지 않습니다.

출력

각 테스트 케이스에 대해, $2, 3, \cdots, n$번 방으로 상자와 리프트를 옮기는 데 필요한 최소 비용을 순서대로 한 줄에 출력합니다. $i$번 방에 대해, 어떻게 옮겨도 $i$번 방으로 옮길 수 없다면 -1을 대신 출력합니다.

문제 풀이