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=teada={1}

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}
edasi={hypped[uus] if uus in hypped else uus for uus in uued }
edasi-=teada
teada.update(edasi)
teada.update(uued)
print(teada, edasi)
#Käivitage, muutke sisendfaili, kontrollige tulemust
#Lisage koodilõik teisel käigul kohtade arvutamiseks
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}
edasi={hypped[uus] if uus in hypped else uus for uus in uued }
edasi-=teada
teada.update(edasi)
teada.update(uued)
print(teada, edasi)
#Proovige kolmas samm
#Pange tsüklisse kuni mängu lõpuni