def liste_adiacenta(tip, fisier):
    with open(fisier) as file:
        info = [[int(elem) for elem in linie.split()] for linie in file.readlines()]
        noduri = info[0][0]
        start = info[0][2]
        liste_adiacenta = [[] for j in range(noduri)]

        info = info[1:]

        if (tip == 'n'):  # graf neorientat
            for muchie in info:
                liste_adiacenta[muchie[0] - 1].append(muchie[1] - 1)
                liste_adiacenta[muchie[1] - 1].append(muchie[0] - 1)
        else:  # graf orientat
            for muchie in info:
                liste_adiacenta[muchie[0] - 1].append(muchie[1] - 1)
        return liste_adiacenta, start

graf, start = liste_adiacenta('o', 'bfs.in')

def bfs(liste_adiacenta, node): #dau ca parametru un nod >=1
    visited = []
    queue = []
    #arborele BF:
    tata = [-1 for nod in range(len(liste_adiacenta))]

    vector_cost = [-1 for i in range(len(liste_adiacenta))]

    visited.append(node-1)
    queue.append(node-1)
    vector_cost[node - 1] = 0

    #print("BFS:", end=' ')
    while queue: #cat timp mai am noduri in coada, i.e. noduri de vizitat
        s = queue.pop(0)    #vizitez primul nod din coada
        #print(s+1, end=' ')

        for n in liste_adiacenta[s]: #adaug vecinii sai in queue pentru a-i vizita ulterior (daca nu au fost deja adaugati
            if n not in visited:
                visited.append(n)
                queue.append(n)
                vector_cost[n] = vector_cost[s]+1
                tata[n] = s
    #print()
    #print("Arbore tati BF:", [i+1 for i in tata])
    return(vector_cost)
vector_cost = bfs(graf, start)
for elem in vector_cost:
    print(elem, end=' ')