문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

예제1-입력

4
1 3
4 3
4 2
1 2

예제1 - 출력

0 0 0 0

예제2-입력

6
1 2
3 4
6 4
2 3
1 3
3 5

예제2 - 출력

0 0 0 1 1 2

예제3-입력

51
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 1
11 44
44 45
45 46
46 47
34 48
48 49
49 50
50 51

예제3 - 출력

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 1 2 3 4

예제4-입력

38
1 2
2 3
3 4
4 5
5 6
6 1
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38

예제4 - 출력

0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

예제5-입력

12
1 3
3 4
4 5
5 6
6 7
7 8
8 4
2 3
7 9
9 12
7 10
10 11

예제5 - 출력

2 2 1 0 0 0 0 0 1 1 2 2

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static LinkedList<Integer>[] subway;
    static boolean[] inCircle;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        subway = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            subway[i] = new LinkedList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            subway[first].add(second);
            subway[second].add(first);
        }
        br.close();

        for (int i = 1; i <= n; i++) {
            inCircle = new boolean[n + 1];
            if (findCircle(i, -1, i))
                break;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 1; i <= n; i++){
            int level = bfs(i);
            bw.append(level + " ");
        }
        bw.flush();
        bw.close();
    }
    static boolean findCircle(int now, int parent, int start) {
        inCircle[now] = true;
        for (int pos : subway[now]) {
            if (!inCircle[pos]) {
                if (findCircle(pos, now, start)) {
                    return true;
                }
            } else if (pos != parent && pos == start){
                return true;
            }
        }
        inCircle[now] = false;
        return false;
    }
    static int bfs(int str){
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[n + 1];

        queue.add(str);
        while (!queue.isEmpty()){
            int now = queue.poll();
            if(inCircle[now]){
                return visited[now];
            }
            for (int v : subway[now]){
                if(visited[v] == 0){
                    visited[v] = visited[now] + 1;
                    queue.add(v);
                }
            }
        }
        return 0;
    }
}