def construieste_liste_adiacenta(n, m, muchii, orientat):
    liste_adiacenta = {i: [] for i in range(1, n + 1)}

    for nod1, nod2 in muchii:
        liste_adiacenta[nod1].append(nod2)
        if not orientat:
            liste_adiacenta[nod2].append(nod1)

    return liste_adiacenta

def afiseaza_liste_adiacenta(liste_adiacenta):
    print("Listele de adiacență:")
    for nod, vecini in liste_adiacenta.items():
        print(f"{nod}: {', '.join(map(str, vecini))}")

def bfs(s, liste_adiacenta, tata, viz, d):
    q = []
    q.append(s)
    viz[s] = 1
    d[s] = 0

    while len(q) > 0:
        x = q.pop(0)
        for j in liste_adiacenta[x]:
            if viz[j] == 0:
                q.append(j)
                viz[j] = 1
                tata[j] = x
                d[j] = d[x] + 1

with open("bfs.in", "r") as f:
    n, m, start = map(int, f.readline().split())
    muchii = [tuple(map(int, line.split())) for line in f]

liste_adiacenta = construieste_liste_adiacenta(n, m, muchii, True)

viz = [0] * (n + 1)
tata = [0] * (n + 1)
d = [-1] * (n + 1)

bfs(start, liste_adiacenta, tata, viz, d)

with open("bfs.out", "w") as output_file:
    for i in range(1, n + 1):
        output_file.write(f'{d[i]} ')