from collections import deque

def citireDate():
    def extrage_numere():
        with open("bfs.in") as f:
            for linie in f:
                for cuvant in linie.split():
                    yield int(cuvant)
    
    gen = extrage_numere()
    
    n = next(gen)
    m = next(gen)
    s = next(gen)

    graf = [[] for i in range(n + 1)]

    for i in range(m):
        x = next(gen)
        y = next(gen)
        graf[x].append(y)

    return n, m, s, graf


def bfs(nod_start, n, graf):
    distante = [-1] * (n + 1)

    distante[nod_start] = 0

    coada = deque([nod_start])

    while coada:
        nod = coada.popleft()
        for vecin in graf[nod]:
            if distante[vecin] == -1:
                distante[vecin] = distante[nod] + 1
                coada.append(vecin)
    return distante


n, m, s, graf = citireDate()

distante = bfs(s,n,graf)

with open("bfs.out", "w") as f:
    rezultat = " ".join(map(str, distante[1:]))
    f.write(rezultat+"\n")