#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 2000001;
int n, m, ans[MAXN], cnt;
struct A{
	int from, to;
}a[MAXN];
struct Edge{
	int next, to;
}edge[MAXN];
bool cmp(A x, A y)
{
	return (x.from < y.from || x.from==y.from&& x.to > y.to);
}

int num_edge, head[MAXN];
void add_edge(int from, int to)
{
	edge[++num_edge].next = head[from];
	edge[num_edge].to = to;
	head[from] = num_edge;
}

void print()
{
	for (int i = 1; i <= n; i ++) printf("%d ",ans[i]);
	printf("\n");
}

bool b[MAXN];
void dfs(int x)
{
	cout << x <<' ';
	ans[++cnt] = x;
	b[x] = 1;
	for (int i = head[x]; i; i = edge[i].next)
		if (!b[edge[i].to])
			dfs(edge[i].to);
}

queue <int> q;
void bfs()
{
	b[1] = 1;
	q.push(1);
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		ans[++cnt] = now;
		for (int i = head[now]; i; i = edge[i].next)
			if (!b[edge[i].to])
			{
				b[edge[i].to] = 1;
				q.push(edge[i].to);
			}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= m; i ++) scanf("%d%d",&a[i].from,&a[i].to);
	sort(a + 1, a + 1 + m, cmp);
	for (int i = 1; i <= m; i ++)
		add_edge(a[i].from, a[i].to);
	dfs(1);
	cout << endl;
	memset(b,0,sizeof(b)); cnt = 0;
	bfs();
	print();
	return 0;
}
/*
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8 
*/