#include<bits/stdc++.h>
using namespace std;
vector<int> v[1000010];
bool vis1[100010];
void dfs(int x){
	if(vis1[x]==true){
		return;
	}
	vis1[x]=true;
	cout<<x<<" ";
	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i]);
	}
}
queue<int> q;
void bfs(){
	bool vis[100010];
	memset(vis,false,sizeof(vis));
	q.push(1);
	vis[1]=true;
	while(!q.empty()){
		int f=q.front();
		cout<<f<<" ";
		for(int i=0;i<v[f].size();i++){
			if(vis[v[f][i]]==false){
				q.push(v[f][i]);
				vis[v[f][i]]=true;
			}
		}
		q.pop();
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
	}
	dfs(1);
	cout<<endl;
	bfs();
	return 0;
}