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