n, m=[int(s) for s in input().split()]
hypped=dict([[int(s) for s in input().split()] for nr in range(m)])
print(hypped)
edasi={1}
teada={1:0}
kaigunr=0
while len(edasi)>0:
    #uued={uuritav+kaik for kaik in range(1, 7)  for uuritav in edasi}
    #uued={uus for uus in uued if uus not in teada and uus <= n}
    kaigunr+=1
    uued=[]
    for uuritav in edasi:
       for kaik in range(1, 7):
          uus=uuritav+kaik
          if uus <= n and uus not in teada:
             uued.append(uus)
             teada[uus]=uuritav
    edasi=set()
    for uus in uued:
      if uus in hypped:
       if hypped[uus] not in teada:
        edasi.add(hypped[uus])
        teada[hypped[uus]]=teada[uus]
      else:
        edasi.add(uus)
    #edasi={hypped[uus] if uus in hypped else uus for uus in uued }
    #edasi-=teada.keys()
    #teada.update(edasi)
    #teada.update(uued)
    print(kaigunr, teada, edasi)
print(kaigunr if n in teada else "EI SAA")
if n in teada:
  koht=n
  while koht:
    print(koht)
    koht=teada[koht]