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, parcurg
    q=[]
    q.append(s)
    viz[s]=1
    d[s]=0
    while len(q)>0:
        x=q.pop(0)
        parcurg.append(x)
        for j in liste_adiacenta[x]:
            if viz[j]==0:
                q.append(j)
                # print(j, end=" ")
                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 matricea 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
parcurg=[]
# Afișăm matricea de adiacență
# afiseaza_liste_adiacenta(liste_adiacenta)
# print("\nBFS(1):")

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