import collections 
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(n)]
#for i in range(m):
for linie in f:
    x, y = [int(a) for a in linie.split()]
    #x,y=map(int,linie.split())
    l[x - 1].append(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()
    for y in l[x]:
        if viz[y] == 0:
            c.append(y)
            viz[y] = 1
            d[y] = d[x] + 1
f = open("bfs.out", "w")
# f.write(" ".join(str(x) for x in d))
for x in d:
    f.write(str(x)+" ")
#f.writelines(map(lambda x:str(x)+' ',d))
f.close()