행성 거리
면접 대비시간 제한20초메모리 제한1024 MB
사이클이 정확히 하나인 연결 그래프에서 각 정점과 그 유일한 사이클 위 정점 사이의 최단 거리를 구한다.
문제
우주에는 N개의 행성이 있고, Google의 우주 부서는 한 행성에서 다른 행성으로 이동할 수 있는 N개의 진공관을 설치했다. 진공관은 양방향이며, 두 행성을 잇는 관을 어느 쪽 행성에서든 사용해 반대쪽 행성으로 이동할 수 있다. 각 진공관은 두 행성을 연결하고, 같은 두 행성을 연결하는 진공관은 없다. 이 관들로 어떤 행성에서든 다른 행성으로 이동할 수 있다. 이 관들 중 일부는 우주에 정확히 하나의 사이클이 존재하도록 연결되어 있다. Google은 이 사이클에 속한 모든 행성에 선물을 숨겨 두었다. 이제 Google은 우주에 있는 각 행성이 선물로부터 얼마나 떨어져 있는지 알고 싶어 한다.
각 행성과 사이클에 속한 행성 사이의 최소 거리(진공관 개수 기준)를 구하라. 사이클에 속한 행성의 거리는 0으로 본다.
입력
첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 행성과 진공관의 수 N이 주어진다. 행성은 1부터 N까지 번호가 붙어 있다.
이어서 N개의 줄이 주어지며, i번째 줄에는 두 정수 xi와 yi가 주어진다. 이는 i번째 진공관이 행성 xi와 행성 yi를 연결한다는 뜻이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 공백으로 구분된 N개의 값으로, i번째 값은 i번째 행성과 사이클에 속한 행성 사이의 최소 거리이다.
제한
- 1 ≤ T ≤ 100.
- 모든 i에 대해 1 ≤ xi ≤ N.
- 모든 i에 대해 1 ≤ yi ≤ N.
- 모든 i에 대해 xi ≠ yi.
- 모든 i ≠ j에 대해 (xi, yi) ≠ (xj, yj).
- 행성을 노드로, 진공관을 간선으로 하는 그래프는 연결되어 있고 사이클이 정확히 하나 존재한다.
힌트
예제 1에서 사이클은 행성 2, 3, 4로 이루어진다. 따라서 행성 2, 3, 4의 거리는 0이다. 행성 1과 2 사이에 진공관이 하나, 행성 3과 5 사이에 진공관이 하나 있다. 그러므로 행성 1과 5는 사이클로부터 거리가 1이다.
예제 2에서는 모든 행성이 사이클에 속한다. 따라서 모든 거리는 0이다.