#include <bits/stdc++.h>
using namespace std;
vector<int> q[100010];
int n,m;
bool vis[100010],vis1[100010];
void dfs(int j){
	cout << j <<" ";
	for(int i=0;i<q[j].size();++i){
        if(!vis[q[j][i]]){
            vis[q[j][i]]=1;
		    dfs(q[j][i]);
        }        
	}
}
void bfs(){
	puts("");
	queue <int> p;
	p.push(1);
	vis1[1]=1;
	while(!p.empty()){
		int j8=p.front(); p.pop();
		cout<<j8<<' ';
		for(int i=0;i<q[j8].size();++i) if(vis1[q[j8][i]]==false) p.push(q[j8][i]),vis1[q[j8][i]]=true;
	}
} 
int main(){
	cin >> n >> m;
	for(int i=1;i<=m;++i){
		int x,y;
		cin >> x >> y;
		q[x].push_back(y);
	}
    vis[1]=1;
    dfs(1);
    bfs();
}