#include <bits/stdc++.h>
using namespace std;
vector<int> vc[1000010];
bool f[100010];
int mx=-1;
queue<int> q;
void dfs(int u)
{
	f[u]=1;
	cout<<u<<" ";
	for(auto x:vc[u])
	{
		if(!f[x])
		{
			f[x]=1;
			dfs(x);
		}
	}
}
void bfs()
{
	int k;
	while(!q.empty())
	{
		k=q.front();
		f[k]=1;
		q.pop();
		for(auto x:vc[k])
		{
			if(!f[x])
			{
				f[x]=1;
				cout<<x<<" ";
				q.push(x);
			}
		}
	}
}
int main()
{
	int n,m,u,v,w;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		vc[u].push_back(v);
	}
	dfs(1);
	cout<<endl;
	q.push(1);
	cout<<1<<" ";
	memset(f,0,sizeof(f));
	bfs();
	return 0;
}