from collections import deque


def construire_lista_adiacenta(f, tip):
    fisier = open(f, "r")
    N, M, S=fisier.readline().split()
    N=int(N)
    M=int(M)
    S=int(S)
    lista=[[] for _ in range(N + 1)]
    for i in range(M):
        x,y=fisier.readline().split()
        x=int(x)
        y=int(y)
        lista[x].append(y)
        if (tip=="neorientat"):
            lista[y].append(x)

    fisier.close()
    return lista, S


lista, S=(construire_lista_adiacenta("bfs.in", 'orientat'))

def BFS(lista, S):
    distanta=[-1]*len(lista)
    distanta[S]=0
    coada=deque([S])

    while coada:
        nod=coada.popleft()
        for vecin in lista[nod]:
            if distanta[vecin]==-1:
                distanta[vecin]=distanta[nod]+1
                coada.append(vecin)

    return distanta

g=open("bfs.out","w")
g.write(" ".join(str(elem) for elem in (BFS(lista, S)[1:])))