from collections import defaultdict

lines = []
with open('bfs.in') as f:
    for line in f:
        line = line.strip().split()
        lines.append(line)

firstline = lines[0]
n = int(firstline[0])
m = int(firstline[1])
s = int(firstline[2])

d = defaultdict(list)
for line in lines[1:]:
    x = int(line[0])
    y = int(line[1])
    d[x].append(y)

import queue
coada = queue.Queue()
vizitat = []
solutie = [0 for nr in range (n+1)]
def bfs(nod):
    coada.put(nod)
    while coada.empty() == False:
        element_curent_coada = coada.get()
        vizitat.append(element_curent_coada)
        for copil in d[element_curent_coada]:
            if copil not in vizitat:
                coada.put(copil)
                solutie[copil]=solutie[element_curent_coada]+1

bfs(2)
for nr in range (1, n+1):
    if nr not in vizitat:
        solutie[nr] = -1
print (solutie[1:])
f = open("bfs.out", "w")
for x in solutie[1:-1]:
    f.write(str(x))
    f.write(" ")
f.write(str(solutie[-1]))
f.close()