rt

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxn = 100001;
using namespace std;
int n,m,u,v;
vector <int> val[maxn];
bool vis[maxn],vis2[maxn];
inline void dfs(int x)
{
	if(!vis[x])
	{
		vis[x]=1;
		printf("%d ",x);
	}
	for(int i=0;i<val[x].size();i++)
	{
		dfs(val[x][i]);
	}
}
inline void bfs(int x)
{
	queue <int > q;
	q.push(x);
	while(!q.empty() )
	{
		int xx=q.front();
		q.pop();
		for(int i=0;i<val[xx].size();i++)
		{
			if(!vis[val[xx][i]])
			{
				vis[val[xx][i]]=1;
				printf("%d ",val[xx][i]);
				q.push(val[xx][i]); 
			}
		}	
	} 
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		val[u].push_back(v); 
	}
	for(int i=1;i<=n;i++) sort(val[i].begin() ,val[i].end() );
	dfs(1);
	printf("\n");
	printf("1 ");
	memset(vis,0,sizeof(vis));
	memset(vis2,0,sizeof(vis2));
	bfs(1);
	return 0;
}