# # lab1 AF
#
# # ex1
# # Scrieți un subprogram pentru construirea în memorie a matricei de adiacență a unui graf
# # (neorientat/orientat în funcție de un parametru trimis subprogramului) citit din fișierul graf.in
# # cu structura precizată mai sus și un subprogram pentru afișarea matricei de adiacență
#
# #voi trimite subprogramului parametrul 0 pt graf orientat si 1 pt neorientat
# def constr_ma(file,param):
#     f=open(file)
#     l=[int(x) for x in f.readline().strip().split()]
#     n=l[0]
#     m=l[1]
#     matrice=[([0]*n)for i in range(n)]
#     for i in range(m):
#         muchie=[int(x) for x in f.readline().strip().split()]
#         if param==0:
#             matrice[muchie[0]-1][muchie[1]-1]=1
#         elif param==1:
#             matrice[muchie[0] - 1][muchie[1] - 1] = 1
#             matrice[muchie[1] - 1][muchie[0] - 1] = 1
#     print(matrice)
#     return matrice
# m=constr_ma( "graf1.in", 1 )
# print('\n')
# def afisare_ma(matrice):
#     for i in range(len(matrice)):
#         for j in range(len(matrice)):
#             if j==len(matrice)-1:
#                 print(matrice[i][j])
#             else:
#                 print(matrice[i][j],end=" ")
#
# afisare_ma(m)
#
#
# #ex2
# #  Scrieți un subprogram pentru construirea în memorie a listelor de adiacență pentru un graf
# # (neorientat/orientat în funcție de un parametru trimis subprogramului) citit din fișierul graf.in
# # cu structura precizată mai sus și un subprogram pentru afișarea listelor de adiacență
#
# def constr_la(file,param):
#     f = open ( file )
#     l = [int ( x ) for x in f.readline ().strip ().split ()]
#     n = l[0]
#     m = l[1]
#     la={}
#     for i in range(m):
#         muchie=[int(x) for x in f.readline().strip().split()]
#         if param==0:
#             if muchie[0] not in la.keys():
#                 la[muchie[0]]=[]
#                 la[muchie[0]].append(muchie[1])
#             else:
#                 la[muchie[0]].append(muchie[1])
#         elif param==1:
#             if muchie[0] not in la.keys() and muchie[1] not in la.keys():
#                 la[muchie[0]] = []
#                 la[muchie[0]].append ( muchie[1] )
#                 la[muchie[1]] = []
#                 la[muchie[1]].append ( muchie[0] )
#             elif  muchie[0] not in la.keys() and muchie[1] in la.keys():
#                 la[muchie[0]] = []
#                 la[muchie[0]].append ( muchie[1] )
#                 la[muchie[1]].append ( muchie[0] )
#             elif  muchie[0] in la.keys() and muchie[1] in la.keys():
#                 la[muchie[0]].append ( muchie[1] )
#                 la[muchie[1]].append ( muchie[0] )
#             elif muchie[0] in la.keys() and muchie[1] not in la.keys():
#                 la[muchie[0]].append ( muchie[1] )
#                 la[muchie[1]] = []
#                 la[muchie[1]].append ( muchie[0] )
#     LA=list(la.keys())
#     LA.sort()
#     la_sortat={i: la[i] for i in LA }
#     return la_sortat
#
# la=constr_la( "graf1.in", 1 )
#
# def afisare_la(la):
#     for key in la.keys():
#         print('{}: '.format(key),end=" ")
#         for val in la[key]:
#             print(val,end=" ")
#         print('\n')
# afisare_la(la)
#
# #ex3
# #3. Implementați algoritmi de trecere de la o modalitate de reprezentare la alta.
# def ma_in_la(matrice):
#     la={}
#     for i in range(len(matrice)):
#         for j in range(len(matrice)):
#             if matrice[i][j]==1:
#                 if i+1 not in la.keys():
#                     la[i+1]=[]
#                     la[i+1].append(j+1)
#                 else:
#                     la[i+1].append(j+1)
#     return la
#
# print(ma_in_la([[0,1,1],[1,0,0],[1,0,0]]))
#
# def la_in_ma(la):
#     n=len(la)
#     ma=[([0]*n)for i in range(n)]
#     for key in la.keys():
#         for val in la[key]:
#             ma[key-1][val-1]=1
#     return ma
#
# print(la_in_ma({1:[2,3],2:[1],3:[1]}))
#
# # B. Parcurgerea în lățime BF
# # 1. a) https://infoarena.ro/problema/bfs
# # b) Se citește în plus (față de a)) de la tastatură două vârfuri s și x. Să se afișeze un drum
# # minim (cu număr minim de arce) de la s la x
# print("\nBFS")
def bfs(file):
    f=open(file)
    linie=f.readline().strip().split()
    n=int(linie[0])
    m=int(linie[1])
    s=int(linie[2])
    la={}
    for i in range(m):
        muchie=f.readline().strip().split()
        x=int(muchie[0])
        y=int(muchie[1])
        if x not in la.keys():
            la[x]=[]
            la[x].append(y)
        else:
            la[x].append(y)
    # LA = list ( la.keys () ) #sortarea va creste complexitatea
    # LA.sort ()
    # la_sortat = {i : la[i] for i in LA}
    vizitat=[0]*n
    vizitat[s-1]=1
    distanta_s=[-1]*n
    coada = [s]
    distanta_s[s-1]=0
    while len(coada)!=0:
        nod_curent=coada.pop(0)
        print(nod_curent)
        for vecin in la[nod_curent]:
            if vizitat[vecin-1]==0:
                distanta_s[vecin - 1] = distanta_s[nod_curent-1]+1
                coada.append(vecin)
                vizitat[vecin-1]=1
    return distanta_s

ds=bfs('bfs.in')
g=open('bfs.out','w')
for i in ds:
    g.write('{} '.format(i))