from collections import deque

adj_list = {}
my_list = []


def add_node(node):
    if node not in my_list:
        my_list.append(node)


def add_edge(node1, node2, my_graph):
    temp = []
    if node1 in my_list and node2 in my_list:
        if node1 not in my_graph:
            temp.append(node2)
            my_graph[node1] = temp
        elif node1 in my_graph:
            temp.extend(my_graph[node1])
            temp.append(node2)
            my_graph[node1] = temp


def read():
    n, m, s = [int(x) for x in f.readline().split()]
    for i in range(1, n + 1):
        add_node(i)
    for i in range(m):
        x, y = [int(z) for z in f.readline().split()]
        if x in adj_list:
            if y not in adj_list[x]:
                add_edge(x, y, adj_list)
        else:
            add_edge(x, y, adj_list)
    return n, m, s


def bfs(my_graph, starting_node):
    # get the shortest distance from starting node to each node in distance
    distance = {}
    for node in my_list:
        distance[node] = -1
    distance[starting_node] = 0
    queue, result = deque(), [starting_node]
    queue.append(starting_node)
    while queue:
        node = queue.popleft()
        aux = []
        if node in my_graph:
            for n in my_graph[node]:
                if n not in result:
                    queue.append(n)
                    aux.append(n)
                    distance[n] = distance[node] + 1
        if aux:
            for each_node in aux:
                result.append(each_node)
    return distance


f = open("bfs.in", "r")
f_out = open("bfs.out", "w")
N, M, S = read()

distance_result = bfs(adj_list, S)
print(distance_result)
sorted_items = sorted(distance_result.items())
for item in sorted_items:
    f_out.write(str(item[1]) + ' ')