from collections import deque

def bfs(N, adj_list, S):
    dist = [-1] * N
    dist[S] = 0
    queue = deque([S])

    # BFS
    while queue:
        node = queue.popleft()
        for neighbor in adj_list[node]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)

    return dist

with open("bfs.in", "r") as f:
    N, M, S = map(int, f.readline().split())
    S -= 1
    adj_list = [[] for _ in range(N)]

    for _ in range(M):
        x, y = map(int, f.readline().split())
        adj_list[x - 1].append(y - 1)

distances = bfs(N, adj_list, S)

with open("bfs.out", "w") as f:
    f.write(" ".join(map(str, distances)) + "\n")