#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m;
bool mmap[10009][10009]={0};
bool vis1[100009]={0};
bool vis2[100009]={0};
queue <int> q;
void dfs(int x){
	cout<<x<<" ";
	for(int i=1;i<=m;i++){
		if(mmap[x][i]&&!vis1[i]){
			vis1[i]=1;
			dfs(i);
		} 
	}
}
void bfs(int x){   
	queue <int> q;  
	q.push(x);  
	cout<<x<<" "; 
	vis2[x]=1; 
	while(!q.empty()){   
		int fro=q.front();  
		for(int i=1;i<m;i++){   
			int point=i;  
			if(!vis2[point]){  
				q.push(point); 
				cout<<point<<" ";
				vis2[point]=1;
			}
		}
		q.pop(); 
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		mmap[x][y]=1;
	}
	vis1[1]=1;
	dfs(1);
	cout<<endl;
	bfs(1);
	return 0;
}