이번 문제는 DFS와 BFS를 활용하여 해결하였다. DFS를 통해 현재 역의 사이클 여부를 확인하고, BFS를 통해 사이클 역에서부터 다른 역까지의 거리를 각각 구하도록 하였다. 그래프 탐색을 위해 인접 리스트로 데이터를 저장하였다.

Code

import sys
sys.setrecursionlimit(10**6)
from collections import deque
n = int(input())
lines = [[] for _ in range(n+1)]
stations = [-1 for _ in range(n+1)]
cycle = [False for _ in range(n+1)]
for _ in range(n):
    a, b = map(int, input().split())
    lines[a].append(b)
    lines[b].append(a)
def chk_cycle(start, cur, cnt):
    if start == cur and cnt >= 2:
        cycle[start] = True
        return
    visited[cur] = True
    for nxt in lines[cur]:
        if not visited[nxt]:
            chk_cycle(start, nxt, cnt+1)
        elif nxt == start and cnt >= 2:
            chk_cycle(start, nxt, cnt)
def get_distance():
    q = deque()
    for i in range(1, n+1):
        if cycle[i]:
            stations[i] = 0
            q.append(i)
    while q:
        cur = q.popleft()
        for nxt in lines[cur]:
            if stations[nxt] == -1:
                stations[nxt] = stations[cur]+1
                q.append(nxt)
for i in range(1, n+1):
    visited = [False for _ in range(n + 1)]
    chk_cycle(i, i, 0)
get_distance()
print(*stations[1:])