from collections import deque
f = open("bfs.in")
#n, m, s = (int(x) for x in f.readline().split())
#n, m, s = [int(x) for x in f.readline().split()]
n,m,s=map(int,f.readline().split())
s -= 1
l = {}
#for i in range(m):
for linie in f:
    #x, y = [int(a) for a in linie.split()]
    x,y=map(int,linie.split())
    if x-1 in l:
        l[x-1].append(y-1)
    else:
        l[x-1]=[y-1]


f.close()
d = [-1] * n
viz = [0] * n
c = deque()
c.append(s)
d[s] = 0
viz[s] = 1
while c:
    x = c.popleft()
    try:
        for y in l[x]:
            if viz[y] == 0:
                c.append(y)
                viz[y] = 1
                d[y] = d[x] + 1
    except:
        pass
f = open("bfs.out", "w")
# f.write(" ".join(str(x) for x in d))
for x in d:
    f.write(str(x))
    f.write(" ")
#f.writelines(map(lambda x:str(x)+' ',d))
f.close()