# from collections import deque, defaultdict
# start = -1
#
# def bfs(graf, start):
#
#     with open("bfs.in", "r") as f:
#         n, m, s = map(int, f.readline().strip().split())
#         for _ in m:
#
#     distante = {}
#     q = [start]
#     distante[start] = 0
#
#     while q:
#         nod_curent = q.pop(0)
#
#         for vecin in graf[nod_curent]:
#             if vecin not in distante:
#                 distante[vecin] = distante[nod_curent] + 1
#                 q.append(vecin)
#
#     for nod in graf:
#         if nod not in distante:
#             distante[nod] = -1
#
#     return distante
#
#
# def citire(file) :
#     with open("bfs.in", 'r') as f:
#         n, m, s = map(int, f.readline().strip().split())
#         start = s
#
#         graf = [[] for _ in range(n+1)]
#
#         for _ in range(m):
#             u, v = map(int, f.readline().strip().split())
#             graf[u].append(v)
#             graf[v].append(u)
#     return graf
#
# #graf = citire("dfs.in")
#
#
# def bfs_minimum_edges(graph, start):
#     distances = {}
#     queue = deque([start])
#     distances[start] = 0
#
#     while queue:
#         current_node = queue.popleft()
#
#         # Iterează prin vecinii nodului curent
#         for neighbor in graph[current_node]:
#             if neighbor not in distances:
#                 distances[neighbor] = distances[current_node] + 1
#                 queue.append(neighbor)
#
#     # Setează distanțele pentru nodurile neatinse la -1
#     for node in graph:
#         if node not in distances:
#             distances[node] = -1
#
#     return distances
#
# def read_graph_from_file(filename):
#     graph = defaultdict(list)
#     with open(filename, 'r') as file:
#         n = int(file.readline().strip())  # Citește numărul de noduri
#         m = int(file.readline().strip())
#         start = file.readline().strip()  # Citește nodul sursă
#
#         for _ in range(n):
#             line = file.readline().strip().split()
#             node = line[0]
#             neighbors = line[1:]
#             graph[node].extend(neighbors)
#
#     return start, graph


from collections import deque


# Funcție pentru BFS care calculează distanțele minime
def bfs(N, adj_list, S):
    dist = [-1] * N  # Inițializăm toate distanțele cu -1
    dist[S] = 0  # Distanța până la nodul sursă este 0
    queue = deque([S])  # Inițializăm coada cu nodul sursă

    # BFS
    while queue:
        node = queue.popleft()
        for neighbor in adj_list[node]:
            if dist[neighbor] == -1:  # Dacă vecinul nu a fost vizitat
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)

    return dist


# Citim datele din fișierul bfs.in
with open("bfs.in", "r") as f:
    N, M, S = map(int, f.readline().split())
    S -= 1  # Convertim nodul sursă la index 0-based
    adj_list = [[] for _ in range(N)]

    # Citim arcele și construim lista de adiacență
    for _ in range(M):
        x, y = map(int, f.readline().split())
        adj_list[x - 1].append(y - 1)  # Convertim la index 0-based

distances = bfs(N, adj_list, S)

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