def construireListeAdiacente(fileName, orientat = False):
    vectorMuchii = []
    for linie in open(fileName, "r").read().split("\n"):
        vectorMuchii.append(linie.split(" "))
    global nrVarfuri
    nrVarfuri= int(vectorMuchii[0][0])
    global nrMuchii
    nrMuchii = int(vectorMuchii[0][1])
    global s
    s = int(vectorMuchii[0][2])
    vectorMuchii.pop(0)
    listaAdiacenta = dict()
    if orientat is False:
        for muchie in vectorMuchii:
            muchie[0] = int(muchie[0])
            muchie[1] = int(muchie[1])
            if muchie[0] not in listaAdiacenta:
                listaAdiacenta[muchie[0]] = []
            if muchie[1] not in listaAdiacenta:
                listaAdiacenta[muchie[1]] = []
            listaAdiacenta[muchie[0]].append(muchie[1])
            listaAdiacenta[muchie[1]].append(muchie[0])
    else:
        for muchie in vectorMuchii:
            muchie[0] = int(muchie[0])
            muchie[1] = int(muchie[1])
            if muchie[0] not in listaAdiacenta:
                listaAdiacenta[muchie[0]] = []
            listaAdiacenta[muchie[0]].append(muchie[1])
    return listaAdiacenta

def afisareListaAdiacenta(listaAdiacenta):
    for varf in sorted(listaAdiacenta.keys()):
        print(f"{varf} adiacent cu {listaAdiacenta[varf]}")

'''Fiind dat un nod S, sa se determine, 
pentru fiecare nod X, numarul minim de arce ce trebuie parcurse 
pentru a ajunge din nodul sursa S la nodul X.

Fisierul de intrare bfs.in contine pe prima linie 3 numere intregi N M S,
 cu semnificatia din enunt. Urmatoarele M linii contin cate doua numere x y, cu 
 semnificatia ca exista arc orientat de la x la y.

In fisierul de iesire bfs.out se vor afla N numere separate prin spatiu cu 
semnificatia ca al i-lea numar reprezinta numarul minim de arce ce trebuie 
 de la nodul S la nodul i.'''

fileIn = "bfs.in"
fileOut = "bfs.out"
s = 0
nrVarfuri = 0
nrMuchii = 0
graf = construireListeAdiacente(fileIn, True)
print(graf)
from collections import deque
def bfs_with_distances(graph, start_node):
    visited = set()  # To keep track of visited nodes
    queue = deque([start_node])  # Queue for BFS
    distance = {start_node: 0}  # Dictionary to store distances from start_node

    while queue:
        node = queue.popleft()

        if node not in visited:
            visited.add(node)

            # Process each neighbor
            for neighbor in graph.get(node, []):
                if neighbor not in distance:  # If neighbor hasn't been visited yet
                    distance[neighbor] = distance[node] + 1  # Distance to neighbor is current distance + 1
                    queue.append(neighbor)

    # Return the dictionary with minimum distances
    return distance
dictionarCost = bfs_with_distances(graf,s)
vectorCost = [-1 for i in range(nrVarfuri)]

for element in sorted(dictionarCost.keys()):
    vectorCost[int(element)-1] = dictionarCost[element]

with open(fileOut,'w') as f:
    for element in vectorCost:
        f.write(str(element) + " ")