def construieste_liste_adiacenta(n, m, muchii, orientat):
    # Inițializăm listele de adiacență cu un dicționar gol pentru fiecare nod
    liste_adiacenta = {i: [] for i in range(1, n + 1)}

    # Adăugăm muchiile în listele de adiacență
    for nod1, nod2 in muchii:
        liste_adiacenta[nod1].append(nod2)

        # Dacă graful este neorientat, adăugăm și nod1 în lista de adiacență a nodului nod2
        if not orientat:
            liste_adiacenta[nod2].append(nod1)

    return liste_adiacenta

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


def bfs(s):
    global 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

# Citim din fisier
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]

# Construim listele de adiacență
liste_adiacenta = construieste_liste_adiacenta(n, m, muchii, True)
viz = [0] * (n + 1)
tata = [0] * (n + 1)
d = [-1] * (n + 1)  # lungime drumuri d[j]=nivel j in arborele parcurgerii d[j]=d[tata[j]]+1

# Aplicăm BFS
bfs(start)

# Deschide un fișier pentru scriere
with open("bfs.out", "w") as output_file:
    for i in range(1, n + 1):
        print(d[i], end=" ", file=output_file)