#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> no(1000010,0);
vector <int> l[1000010];
int n,m;
void dfs(int k){
	vector <int> o;
    for(int i=0;i<l[k].size();i++){
        if(no[l[k][i]]==0){
            no[l[k][i]]=1;
            o.push_back(l[k][i]);
        }
    }
    sort(o.begin(),o.end());
    for(int i=0;i<o.size();i++){
    	cout<<o[i]<<' ';
	    dfs(o[i]);
	}
}
void bfs(int k){
	vector <int> o;
	for(int i=0;i<l[k].size();i++){
		if(no[l[k][i]]==0){
            no[l[k][i]]=1;
            o.push_back(l[k][i]);
        }
	}
	sort(o.begin(),o.end());
	for(int i=0;i<o.size();i++){
    	cout<<o[i]<<' ';
	}
	for(int i=0;i<o.size();i++){
    	bfs(o[i]);
	}
}
int main(){
    int x,y;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        l[x].push_back(y);
    }
    cout<<1<<' ';
    dfs(1);
    cout<<'\n';
    vector<int> v(1000010,0);
    no=v;
    cout<<1<<' ';
    bfs(1);
    return 0;
}