#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
int n,m,x,y,pre[100100];
queue<int>q;
vector<int>v[100100];
struct node{
	int x,y;
}a[1001000];
bool cmp(node a , node b)
{
	return a.y<b.y;
}
void dfs(int x)
{
	if(pre[x]==1)
		return ;
	pre[x]=1;
    cout<<x<<" ";
	for(int i=0 ; i<v[x].size() ; ++i)
		if(pre[v[x][i]]==0)
			dfs(v[x][i]);
}

void bfs(int x)
{
	q.push(1);
	pre[x]=1;
	while(q.size()!=0)
	{
		int y=q.front();q.pop();
        cout<<y<<" ";
		for(int i=0 ; i<v[y].size() ; ++i)
		{
			if(pre[v[y][i]]==0)
			{
				q.push(v[y][i]);
				pre[v[y][i]]=1;
			}
		}
	} 
}
int main()
{
	cin>>n>>m;
	for(int i=1 ; i<=m ; ++i)
	cin>>a[i].x>>a[i].y;
	sort(a+1 , a+1+n ,cmp);
	for(int i=1 ; i<=m ; ++i)
	v[a[i].x].push_back(a[i].y);
	dfs(1);
	cout<<endl;
	memset(pre , 0 , sizeof(pre));
	bfs(1);
	return 0;
# }