행성 거리

우주에는 N개의 행성이 있으며, Google의 우주 사업부는 한 행성에서 다른 행성으로 이동할 수 있는 N개의 진공관을 설치했다. 진공관은 양방향이므로, 여행자는 두 행성 사이의 진공관을 이용해 어느 한 행성에서 다른 행성으로 이동할 수 있다. 각 진공관은 두 행성을 연결하며, 같은 행성 쌍을 연결하는 두 진공관은 없다. 이 진공관들은 그중 하나 이상을 이용해 어떤 행성에서든 다른 어떤 행성으로든 이동할 수 있도록 행성들을 연결한다. 이 진공관 중 일부는 우주에 정확히 하나의 사이클이 존재하도록 연결되어 있다. Google은 이 사이클에 속한 모든 행성에 선물을 숨겨 두었다. 이제 Google은 우주의 각 행성이 선물로부터 얼마나 멀리 떨어져 있는지 알고 싶어 한다.

각 행성과 사이클에 속한 행성 사이의 최소 거리(진공관 개수 기준)를 구해야 한다. 사이클에 속한 행성은 거리가 0인 것으로 간주한다.

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1 GB. 모든 i에 대해 1 ≤ $x_{i}$ ≤ N. 모든 i에 대해 1 ≤ $y_{i}$ ≤ N. 모든 i에 대해 $x_{i}$ ≠ $y_{i}$. 모든 i ≠ j에 대해 ($x_{i}$, $y_{i}$) ≠ ($x_{j}$, $y_{j}$).

행성을 정점으로, 진공관을 간선으로 하는 그래프는 연결되어 있으며 정확히 하나의 사이클을 갖는다.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ N ≤ 30.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 1000.

첫 번째 줄에는 테스트 케이스의 수인 정수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 행성과 진공관의 수인 정수 N이 주어진다. 행성에는 1부터 N까지 번호가 매겨져 있다. 이어지는 N개의 줄 중 i번째 줄에는 두 정수 $x_{i}$와 $y_{i}$가 주어지며, 이는 i번째 진공관이 행성 $x_{i}$와 행성 $y_{i}$를 연결한다는 뜻이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 공백으로 구분된 N개의 값으로 이루어진 목록이다. 이 목록의 i번째 값은 i번째 행성과 사이클에 속한 행성 사이의 최소 거리를 나타낸다.

예제 케이스 #1에서 사이클은 행성 2, 3, 4로 이루어진다. 따라서 행성 2, 3, 4의 거리는 0이다. 1와 2 사이에 진공관이 있고, 3와 5 사이에도 진공관이 있다. 따라서 행성 1와 5는 사이클로부터 거리 1에 있다.

예제 케이스 #2에서는 모든 행성이 사이클에 속한다. 따라서 이들의 거리는 0이다.