#https://infoarena.ro/problema/bfs

import pprint as pp

f = open("bfs.in", "r")
g = open("bfs.out", "w")

l = f.readlines()

#scoatem (n,m) si muchiile
l = [x.split() for x in l]
l = [list(map(int, x)) for x in l]

n, m, nod_start = l[0]

muchii = l[1:]

listaAdiacenta = {x: [] for x in range(1, n + 1)}

for pair in muchii:
    listaAdiacenta[pair[0]].append(pair[1])

visited = [0 for _ in range(n)]
shortestPath = [0 for _ in range(n)]

Q = [nod_start]
visited[nod_start - 1] = 1

while Q:
    crtNode = Q[0]
    del(Q[0])
  #  print(crtNode)

    for vecin in listaAdiacenta[crtNode]:
        if not visited[vecin - 1]:
            Q.append(vecin)
            visited[vecin - 1] = 1
            shortestPath[vecin - 1] = shortestPath[crtNode - 1] + 1
    
for i in range(n):
    if not visited[i]: 
        shortestPath[i] = -1

for i in shortestPath:
    g.write(str(i) + " ")