from collections import defaultdict, deque
def read_graph(filename):
    with open(filename, "r") as file:
        lines = file.readlines()
        N, M, S = map(int, lines[0].split())
        edges = [tuple(map(int, line.split())) for line in lines[1:]]
    adjacency_list = defaultdict(list)
    for u, v in edges:
        adjacency_list[u].append(v)
    return N, M, S, adjacency_list

def bfs(N, S, adjacency_list):
    distances = [-1] * (N + 1)
    distances[S] = 0
    queue = deque([S])

    while queue:
        current = queue.popleft()
        for neighbor in adjacency_list[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)

    return distances[1:]

def write_output(filename, distances):
    with open(filename, "w") as file:
        file.write(" ".join(map(str, distances)) + "\n")

if __name__ == "__main__":
    input_file = "bfs.in"
    output_file = "bfs.out"

    N, M, S, adjacency_list = read_graph(input_file)

    distances = bfs(N, S, adjacency_list)

    write_output(output_file, distances)