from queue import Queue
f = open("bfs.in")
N,M,S = f.readline().split()
N,M,S = int(N),int(M),int(S)

culoare = {}
muchii = {}
counter_n = {}

for i in range(1,N+1):
    culoare[i] = 0
    counter_n[i] = -1

for line in f:
    a,b = line.split()
    a,b = int(a),int(b)
    if a in muchii.keys():
        muchii[a].append(b)
    else:
        muchii[a] = [b]

print(muchii)
q = Queue(maxsize = N)
q.put(S)
counter_n[S] = 0
culoare[S] = 2
while(not q.empty()):
    element = q.get()
    culoare[element] = 2
    print(element)
    for i in muchii[element]:
        if culoare[i] == 0:
            counter_n[i] = counter_n[element]+1
            q.put(i)
            culoare[i]=1

with open("bfs.out","w") as w:
    for i in counter_n:
        w.write(f"{counter_n[i]} ")

f.close()