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):
    temp = []
    if node1 in my_list and node2 in my_list:
        if node1 not in adj_list:
            temp.append(node2)
            adj_list[node1] = temp
        elif node1 in adj_list:
            temp.extend(adj_list[node1])
            temp.append(node2)
            adj_list[node1] = temp


def bfs(starting_node):
    visited, queue, result = {starting_node}, deque([starting_node]), [[starting_node]]
    while queue:
        node = queue.popleft()
        aux = []
        if node in adj_list:
            for n in adj_list[node]:
                if n not in visited:
                    queue.append(n)
                    visited.add(n)
                    aux.append(n)
            if aux:
                result.append(aux)
    return result


f = open("bfs.in", "r")
f_out = open("bfs.out", "w")
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()]
    add_edge(x, y)

bfs_result = bfs(S)

print(bfs_result)

for i in range(1, N+1):
    ok = 0
    for j in bfs_result:
        for k in j:
            if i == k:
                f_out.write(str(bfs_result.index(j)) + " ")
                ok = 1
    if ok == 0:
        f_out.write("-1 ")