```c
#include<bits/stdc++.h>
#define ll long long 

using namespace std;
ll n,m;
queue<ll> dl;
bool u1[100005],u2[100005];
vector<ll> p[100005];
void DFS(ll x){
	cout<<x<<" ";
	for(ll i=0;i<p[x].size();i++){
		if(!u1[p[x][i]]){
			u1[p[x][i]]=true;
			DFS(p[x][i]);
		}	
	}
}
void BFS(){
	while(!dl.empty()){
		ll x=dl.front();
		dl.pop();
		cout<<x<<" ";
		for(ll i=0;i<p[x].size();i++){
			if(!u2[p[x][i]]){
				u2[p[x][i]]=true;
				dl.push(p[x][i]);		
			}
		}	
	}
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		p[u].push_back(v);
	}
	u1[1]=true;
	u2[1]=true;
	dl.push(1);
	DFS(1);
	cout<<endl;
	BFS();
	
	return 0;
}