from collections import defaultdict, deque

#citirea datelor de intrare
with open("bfs.in", "r") as f:
    N, M, S = map(int, f.readline().split())
    graf = defaultdict(list)
    for _ in range(M):
        x, y = map(int, f.readline().split())
        graf[x].append(y)

#functia care calculeaza distantele minime folosind bfs
def bfs(graf, start, N):
    distante = [-1] * (N + 1)
    distante[start] = 0
    q = deque()
    q.append(start)

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

    return distante

distante_minime = bfs(graf, S, N)

#scriem rezultatele in fisierul de iesire
with open("bfs.out", "w") as g:
    g.write(" ".join(map(str, distante_minime[1:])))