#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
struct hhh
{
	int x,y;
}node[1000010];
int n,m,root;
vector<int> a[1000010];
queue<int> q;
int vis[100010],cnt,flag=0;
int cmp(hhh x,hhh y)
{
	if(x.x!=y.x)
		return x.x<y.x;
	return x.y<y.y;
}
void dfs(int x)
{
	vis[x]=1;
	cnt++;
	if(flag==0)
		cout<<x<<" ";
	if(cnt>=n)
	{
		flag=1;
		return ;
	}
	for(int i=0;i<a[x].size();i++)
		if(vis[a[x][i]]==0)
			dfs(a[x][i]);
	return ;
}
void bfs(int x)
{
	q.push(x);
	while(!q.empty())
	{
		int f=q.front();
		q.pop();
		cout<<f<<" ";
		for(int i=0;i<a[f].size();i++)
			if(vis[a[f][i]]==0)
			{
				q.push(a[f][i]);
				vis[a[f][i]]=1;
			}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>node[i].x>>node[i].y;
	sort(node+1,node+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		a[node[i].x].push_back(node[i].y);
		vis[node[i].y]=1;
	}
	for(int i=1;i<=n;i++)
		if(vis[i]==0)
			root=i;
	memset(vis,0,sizeof(vis));
	dfs(root);
	cout<<endl;
	memset(vis,0,sizeof(vis));
	bfs(root);
	return 0;
}