Under construction

Still being built. Things may change

Seoul Subway Line 2

Interview

Time limit2sMemory limit512 MB

Summary
Given a connected graph with N vertices and N edges (exactly one cycle), find each vertex's distance to the unique cycle.
Level

Medium6 of 10

Topics
Graph, BFS, Implementation, Queue
Solved
No attempts yet

Problem

Seoul Subway Line 2 looks like this.

Line 2 has 51 stations and 51 segments connecting pairs of stations. In other words, it can be represented as a graph with 51 vertices and 51 bidirectional edges. Line 2 consists of one circular line and two branches. A route on which, starting from some station and continuing onward, you can always return to the starting station is called a circular line. A branch is a tree-shaped route that begins at a station belonging to the circular line.

The distance between two stations (vertices) is the number of segments (edges) you must pass through. The distance between station A and the circular line is the minimum distance between A and a station belonging to the circular line.

Given a route map of the same shape as Line 2, find the distance between each station and the circular line.

Input

The first line gives the number of stations N (3 ≤ N ≤ 3,000). Each of the next N lines gives information about a segment connecting two stations. The same segment is never given more than once, and stations are numbered from 1 to N. Only routes in which a path always exists between any two stations are given as input.

Output

Print N integers in total. Print the distance between station 1 and the circular line, the distance between station 2 and the circular line, ..., the distance between station N and the circular line, separated by spaces.

Examples5

  1. Example 1

    Input
    4
1 3
4 3
4 2
1 2
    Expected output
    0 0 0 0

  2. Example 2

    Input
    6
1 2
3 4
6 4
2 3
1 3
3 5
    Expected output
    0 0 0 1 1 2

  3. Example 3

    Input
    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
    Expected output
    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. Example 4

    Input
    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
    Expected output
    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. Example 5

    Input
    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
    Expected output
    2 2 1 0 0 0 0 0 1 1 2 2