#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct aoligei{
    int head,tail; 
};
vector <aoligei> a;
vector <int> f[100001];
int i,n,j,k,m,l,o,p;
bool dfsflag[100001]={0},bfsflag[100001]={0};
bool px(aoligei x,aoligei y)
{
	if(x.tail==y.tail) 
	return x.head<y.head;
	else return x.tail<y.tail;
}
void dfs(int start1)
{
    dfsflag[start1]=1;
	cout<<start1<<' ';
	for(i=0;i<f[start1].size();i++)
	{
		int back1=a[f[start1][i]].tail;
		if(!dfsflag[back1]) {
		    dfs(back1);
		}
	}
}
void bfs(int start2)
{
	queue <int> q;
	q.push(start2);
	cout<<start2<<' ';
	bfsflag[start2]=true;
	while(!q.empty())
	{
		    int fr=q.front();
		    for(i=0;i<f[fr].size();i++)
		    {
			    int back2=a[f[fr][i]].tail;
			    if(bfsflag[back2]==false)
			    {
				    q.push(back2);
				    cout<<back2<<' ';
				    bfsflag[back2]=true;
			    }
		    }
		q.pop();
	}
}
int main()
{
	cin>>n>>m;
	for(i=0;i<m;i++)
	{
		int u,v;
		aoligei ls;
		cin>>u>>v;
		ls.head=u;ls.tail=v;
		a.push_back(ls);
	}
	sort(a.begin(),a.end(),px);
	for(i=0;i<m;i++)
	{
		f[a[i].head].push_back(i);
	}
	dfs(1);cout<<endl;bfs(1);cout<<endl;
	return 0;
}```