import collections

# bfs infoarena

def lista_sursa(nume):
    f = open(nume)
    n, m, s = [int(x) for x in f.readline().split()]

    s = s - 1 # scadem 1 pentru ca incepem de la 0 cu vectorul

    la = [ [] for i in range(n)] # lista arce

    for i in range(1,m):
        x, y = [int(x) for x in f.readline().split()]
        la[x-1].append(y-1)
    f.close()
    return n, m, s, la

def bfs(s):
    c = collections.deque()
    c.append(s)
    d[s] = 0
    viz[s] = 1
    while c :
        x = c.popleft() # scaotem un nod din coada, ii luam vecinii
        for y in la[x] :
            if viz[y] == 0:
                c.append(y)
                viz[y] = 1
                d[y] = d[x] + 1


n, m, s, la = lista_sursa("bfs.in")
d = [-1 for i in range(n)] # distanta de la nodul sursa la celelalte
viz = [0 for i in range(n)] # vectorul de vizitati
bfs(s)
w = open("bfs.out", "w")

for i in d:
    w.write(str(i) + " ")