#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;//点 
const int M=1e6+10;//边

int h[N],e[M],ne[M],idx=0;
int dpath[N],bpath[N];
bool st[N],bst[N];
int dcnt=1,bcnt=0;
queue<int> q;

void add(int a,int b)//建邻接表 
{
	if(h[a]==-1){
		e[idx]=b;
		ne[idx]=h[a];
		h[a]=idx++;
	}
	else{
		int temp=h[a];
		bool first_flag=false;
		bool last_flag=false;
		for(int i=h[a];i!=-1;i=ne[i]){
			if(b<e[i]&&!first_flag){
				e[idx]=b;
				ne[idx]=h[a];
				h[a]=idx++;				
			}
			if(b<e[i]){
				e[idx]=b;
				ne[idx]=i;
				ne[temp]=idx++;
				last_flag=true;
				break;
			}
			temp=i;
			first_flag=true;
		} 
		if(!last_flag){
			e[idx]=b;
			ne[idx]=ne[temp];
			ne[temp]=idx++;
		}	
	}
}

void dfs(int s){
	if(h[s]==-1){
		return;
	}
	for(int i=h[s];i!=-1;i=ne[i])//注意是i!=-1 否则会少遍历一个点 
	{
		int next=e[i];
		if(!st[next]){
			st[next]=true;
			dpath[dcnt++]=next;
//			printf("********%d\n",path[cnt-1]);
			dfs(next);
//			st[next]=false;
		}
	}
//	cout<<"bye"<<endl;
	return;
}

void bfs(int s){
	if(q.empty()){
		return;
	}
	for(int i=h[s];i!=-1;i=ne[i]){
		if(!bst[e[i]]){
			q.push(e[i]);
			bst[e[i]]=true;			
		}

	}
	
	bpath[bcnt++]=q.front();
	q.pop();
	int next=q.front();
	bfs(next);
	
}

int main(void){
	int n,m;
	memset(h,-1,sizeof h);
	
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	dpath[0]=1;
	dfs(1);
	for(int i=0;i<n;i++){
		printf("%d ",dpath[i]);
	}
	printf("\n");
	q.push(1);
//	bpath[0]=1;
	bfs(1);
		for(int i=0;i<n;i++){
		printf("%d ",bpath[i]);
	}
	return 0;
}