from collections import defaultdict

with open("bfs.in.txt", '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 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 visited[ self.graph[s][i] ] == False:
                    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.txt", 'w') as fout:
            for i in range(1, N+1):
                if visited[i] == True:
                    fout.write('%s ' % lista_costuri[i])
                else:
                    fout.write('%s ' % "-1")
            fout.close()


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

g.BFS(S)