#include<bits/stdc++.h>
using namespace std;
#define N 1000005
vector<int> p[N];
queue<int> q;
bool u[N];
bool b[N];
int j = 0; 
void fun1(int n){
	cout<<n<<" ";
	for(int i = 0;i<p[n].size();++i){
		if(!u[p[n][i]]){
			u[p[n][i]]=true;
			++j;
			fun1(p[n][i]);
		}
	}
}
void fun2(int n){
	b[n]=true;
	q.push(n);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		cout<<x<<" ";
		for(int i = 0;i<p[x].size();i++){
			if(!b[p[x][i]]){
				b[p[x][i]]=true;
				q.push(p[x][i]);
			}
			
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 0;i<m;i++){
		int k , l;
		cin>>k>>l;
		p[k].push_back(l);
	}
	u[1]=true;
	fun1(1);
	cout<<endl;
	int i = 0;
	fun2(1);
	return 0;
}