n, m=[int(s) for s in input().split()]
hypped=dict([[int(s) for s in input().split()] for nr in range(m)])
uurida=[1]
tuvastatud=[1]
kusttulin={};
while len(uurida)>0:
 uuritav=uurida.pop(0)
 for samm in range(1, 7):
  koht=uuritav+samm
  print(koht)
  if (koht <= n) and (koht not in tuvastatud):
    tuvastatud.append(koht)
    kusttulin[koht]=[uuritav, samm]
    if koht in hypped:
      print("ka ", hypped[koht])
      if hypped[koht] not in tuvastatud:
        tuvastatud.append(hypped[koht])
        kusttulin[hypped[koht]]=[uuritav, samm]
        uurida.append(hypped[koht])
    else:
      uurida.append(koht)
 print(uurida, tuvastatud)
print(kusttulin)
#exit()
#Kuvage, kas jõuti lõppu.
print("Jah" if n in tuvastatud else "Ei")
  #Näita, milliselt ruudult veeretati võidukäik
if n in tuvastatud:
  print("koht enne lõppu: ", kusttulin[n][0])
  koht=n
  while koht!=1:
    veeretus=kusttulin[koht][1]
    koht=kusttulin[koht][0]
    print(koht, veeretus)
#Kuvage ruudud, millelt veeretati lõppu jõudmise teekonnal
#Katseks looge ka sisendfail, kus ei pääse lõppu