#include<bits/stdc++.h>
using namespace std;
vector<list<int>> tu(100005);//邻接表
queue<int> q;
int n,m,vis[100005],ans;
void dfs(int x){
    cout<<x<<" ";
	vis[x]=1;
	int http[100005],cnt=0;
	for(int i:tu[x])    http[++cnt]=i;
	sort(http+1,http+cnt+1);
	for(int i=1;i<=cnt;i++) if(vis[http[i]]==0) dfs(http[i]);
}
void bfs(int x){
    cout<<x<<" ";
    vis[x]=1;
	q.push(x);
	while(!q.empty()){
	    int http[100005],cnt=0;
    	for(int i:tu[q.front()])    http[++cnt]=i;
        sort(http+1,http+cnt+1);
    	for(int i=1;i<=cnt;i++){
    	    if(vis[http[i]]==0){
    	        cout<<http[i]<<" ";
    	        q.push(http[i]);
    	        vis[http[i]]=1;
    	    }
    	}
    	q.pop();
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){//输入 
    	int x,y;
    	cin>>x>>y;
    	tu[x].push_back(y);//邻接表 
	}
	dfs(1);
	cout<<endl;
	for(int i=1;i<=n;i++){
	    vis[i]=0;
	}
	bfs(1);
    return 0;
}