from collections import deque

class Nod:
  def __init__(self, inf, par=None):
    self.informatie = inf
    self.parinte = par
  
  def drumRadacina(self):
    nod = self
    lst = []

    while nod != None:
      lst.append(nod)
      nod = nod.parinte
    lst.reverse()

    return lst
  
  def vizitat(self):
    nod = self.parinte

    while nod != None:
      if nod.informatie == self.informatie:
        return True
      nod = nod.parinte
      
    return False

  def __repr__(self):
    return "{} ({})".format(self.informatie, " -> ".join(str(e) for e in self.drumRadacina()))
  
  def __str__(self):
    return "{}".format(self.informatie)


class Graf:
  def __init__(self, listaAdj, start, scopuri): 
    self.listaAdj = listaAdj
    self.start = start
    self.scopuri = scopuri

  def scop(self, informatieNod):
    return informatieNod in [scop.informatie for scop in self.scopuri]
  
  def succesori(self, nod):
    listaSuccesori = []
    
    for vecin in self.listaAdj[nod]:
      nodNou = Nod(vecin.informatie, nod)
      if not nodNou.vizitat():
        listaSuccesori.append(nodNou)
    
    return listaSuccesori

n0 = Nod(0)
n1 = Nod(1, n0)
n3 = Nod(3, n0)
n4 = Nod(4, n0)
n2 = Nod(2, n1)
n5 = Nod(5, n1)
n6 = Nod(6, n3)
n7 = Nod(7, n4)
n8 = Nod(8, n7)
n9 = Nod(9, n7)

graf = Graf({n0: [n1, n3, n4], n1: [n0, n2, n5], n2: [n1, n5, n7], n3: [n0, n6], n4: [n0, n7], n5: [n1, n2], n6: [n3], n7: [n4, n8, n9], n8: [n7], n9: [n7]}, n0, [n5, n9])

def bfs(graf, nrsol):
  start = graf.start
  q = deque()
  q.append(start)
  nr = 0

  while q:
    node = q.popleft()

    if graf.scop(node.informatie):
      print(node.drumRadacina())
      nr += 1
      if nr == nrsol:
        return 
    else:
      for vecin in graf.succesori(node):
        if not vecin.vizitat():
          q.append(vecin)

bfs(graf, 1)