from collections import defaultdict

with open("bfs.in", 'r') as f:
    lines = f.readlines()
    N, M, S = [int(val) for val in lines[0].split()]
f.close()

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)


    def addEdge(self, u, v):
        self.graph[u].append(v)


    # def PrintGraph(self):
    #     print("Edges of Graph:")
    #     for node in self.graph:
    #         for neighbour in self.graph[node]:
    #             print(f"({node}, {neighbour})", end = " ")
    #         print()


    def BFS(self, s):
        # Toate nodurile nevizitate
        visited = [False] * (max(self.graph) + 1)
        queue = []
        #nod sursa = visitat + in coada
        queue.append(s)
        visited[s] = True
        lista_costuri = [0] * (N+1)

        while queue:
            #deque nod
            s = queue.pop(0)
            # parcurgem vecinii, pe cei nevizitati ii marcam si ii introducem in queue
            for i in range(0, len(self.graph[s])):
                if not visited[ self.graph[s][i] ]:
                    queue.append(self.graph[s][i])
                    visited[self.graph[s][i]] = True
                    lista_costuri[self.graph[s][i]] = lista_costuri[s] + 1


        with open("bfs.out", 'w') as fout:
            for i in range(1, N+1):
                if visited[i]:
                    fout.write('%s ' % lista_costuri[i])
                else:
                    fout.write('%s ' % "-1")
            fout.close()


g = Graph()

for i in range(1, M + 1):
    node1, node2 = [int(val) for val in lines[i].split()]
    g.addEdge(node1, node2)
#graf creat

g.BFS(S)