24396번 - 푸앙이와 별

중앙대학교의 자랑스러운 청룡 푸앙이는 자신만의 별을 가지고 있다. N개의 꼭짓점과 $\frac{N(N - 1)}{2}$개의 간선으로 이루어진 별은 무방향 완전 그래프이기 때문에 아름다운 모양을 띤다.

푸앙이는 모든 꼭짓점 간의 거리가 1이라는 사실에 매료되었다. 그러나 푸앙이를 싫어하는 명진이는 푸앙이의 별의 간선들 중 몇 개를 잘라버렸다. 푸앙이는 좌절했지만, 새로운 별에도 매력을 느끼기 위해 꼭짓점 간의 거리를 계산하기로 했다. 푸앙이를 도와 꼭짓점 간의 거리를 계산해주자!

첫째 줄에 별을 이루는 꼭짓점의 개수 N(2 ≤ N ≤ 300,000)과 명진이가 간선을 자르는 연산을 수행한 횟수 M(1 ≤ M ≤ 300,000)이 주어진다.

이후 M개의 줄에 걸쳐 정수 A_i와 B_i(1 ≤ A_i, B_i ≤ N, A_i ≠ B_i)가 주어지며, 다음과 같은 의미를 가진다.

• A_i번과 B_i번 꼭짓점을 잇는 간선을 자른다. 그런 간선이 이미 잘려 있다면 무시한다.

첫째 줄부터 N개의 줄에 걸쳐, i번 줄엔 1번 정점으로부터 i번 정점까지의 최단 거리를 출력한다. 경로가 존재하지 않는 경우에는 -1을 출력한다.

무방향 완전 그래프는 서로 다른 두 정점이 반드시 하나의 무방향 간선으로 연결되어 있는 그래프를 말한다.