from collections import *
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
for i in g:
    i.sort()
dfsres = [1]

dfsarr = set([1])
def dfs(x):
    for i in g[x]:
        if i not in dfsarr:
            dfsarr.add(i)
            dfsres.append(i)
            dfs(i)


bfsres = [1]
bfsarr = set([1])

def bfs(x):
    q = deque()
    q.append(x)
    while q:
        p = q.popleft()
        for i in g[p]:
            if i not in bfsarr:
                q.append(i)
                bfsarr.add(i)
                bfsres.append(i)


dfs(1)
bfs(1)
for i in dfsres:
    print(i,end = ' ')
print()
for i in bfsres:
    print(i,end = ' ')