#deque din collections e mai eficient decat vector - popleft in O(1) vc pop(0) in O(n)

from collections import deque


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 _ 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', 'infoarena.in')


def bfs(liste_adiacenta, node):
    vector_cost = [-1 for _ in range(len(liste_adiacenta))]  # distanțe inițial -1 (noduri nevizitate)
    queue = deque([node - 1])  # coada cu nodul sursă (numerotare de la 0)

    vector_cost[node - 1] = 0  # distanța la sine este 0

    while queue:
        s = queue.popleft()  # scoatem primul element din coadă

        for n in liste_adiacenta[s]:
            if vector_cost[n] == -1:  # dacă nodul n nu a fost vizitat
                queue.append(n)
                vector_cost[n] = vector_cost[s] + 1  # actualizăm distanța

    return vector_cost


vector_cost = bfs(graf, start)
with open("bfs.out", "w") as file:
    file.write(" ".join(map(str, vector_cost)))
#print(" ".join(map(str, vector_cost)))

'''

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=' ')

'''