n, m=[int(s) for s in input().split()]
paarid=[]
for nr in range(m):
  abi=[]
  for s in input().split():
    abi.append(int(s))
  paarid.append(abi)
print(paarid)
hypped=dict(paarid)
#hypped=dict([[int(s) for s in input().split()] for nr in range(m)])
print(hypped)
edasi=teada={1}
uued=set()
for uuritav in edasi:
  for kaik in range(1, 7): 
    uued.add(uuritav+kaik)
#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)