from queue import Queue
fin = open("bfs.in", "r")
string = fin.readline()
s = [int(x) for x in string.split()]
vertices, edges, source = s
g = [[] for x in range(vertices + 1)]
for i in range(edges):
    string = fin.readline()
    s = [int(x) for x in string.split()]
    first, last = s
    g[first].append(last)

def BFS(lst, nrOfVertices, startNode, outputFile):
    fout = open(outputFile, "w")
    dist = [-1] * (nrOfVertices + 1)
    dist[startNode] = 0
    q = Queue(maxsize=nrOfVertices)
    q.put(startNode)
    while not q.empty():
        node = q.get()
        lengthOfList = len(lst[node])
        for i in range(lengthOfList):
            if dist[lst[node][i]] == -1:
                dist[lst[node][i]] = 1 + dist[node]
                q.put(lst[node][i])

    for i in range(1, nrOfVertices + 1):
        fout.write(str(dist[i]) + " ")
    fout.write("\n")
    fout.close()


BFS(g, vertices, source, "bfs.out")