#include<bits/stdc++.h>
#define N 100010
#define M 1000010

using namespace std;
int m,n;

vector<int> h[N];
int dvis[N],bvis[N];
int dpath[N],didx,bpath[N],bidx;

void init(){
	
}

void addEdge(int a,int b){
	h[a].push_back(b);
}

void dfs(int now){//图的dfs是非回溯的dfs 
	for(vector<int>::iterator it=h[now].begin();it!=h[now].end();it++){
		int k = *it;
		if(!dvis[k]){//查重 
			//递去
			dpath[didx++]=k; 
			dvis[k]=1;
			dfs(k); 
		} 
	}
}

queue<int> q;
void bfs(int st){
	bvis[st]=1;
	bpath[bidx++]=st;
	q.push(st);
	
	while(!q.empty()){
		int now=q.front();q.pop();
		for(vector<int>::iterator it=h[now].begin();it!=h[now].end();it++){
			int k= *it;
			if(!bvis[k]){
				bpath[bidx++]=k;
				bvis[k]=1;
				q.push(k);
			} 
		}
	}
}

int main(){
	cin>>n>>m;
	while(m--){
		int a,b;cin>>a>>b;
		addEdge(a,b);
	}
	for(int i=1;i<=n;i++) sort(h[i].begin(),h[i].end());//对每个点的邻接点排序 
	
	//dfs
	dpath[didx++]=1;
	dvis[1]=1;
	dfs(1);
	//bfs
	bfs(1);
	
	for(int i=0;i<n;i++) cout<<dpath[i]<<' ';
	cout<<'\n';
	for(int i=0;i<n;i++) cout<<bpath[i]<<' ';
	return 0;
}