#include<bits/stdc++.h>
using namespace std;
int x,y,n,m;
bool vis[100005],viis[100005];
vector<int> ans[100005];
void dfs(int k){
	cout<<k<<" " ;
	for(int i=0;i<ans[k].size();i++){
		if(vis[ans[k][i]]==0){
			vis[ans[k][i]]=1;
			dfs(ans[k][i]);
		}
	}
}
void bfs(int k){
	queue<int> q;
	q.push(k);
	while(q.size()!=0){
		int t=q.front();
		cout<<t<<" ";
		for(int i=0;i<ans[t].size();i++){
			if(viis[ans[t][i]]==0){
				viis[ans[t][i]]=1;
				q.push(ans[t][i]);
			}
		}
		q.pop();
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		ans[x].push_back(y);
	}
	vis[1]=1;
	dfs(1);
	cout<<endl;
	viis[1]=1;
	bfs(1);
	return 0;
}