#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
int n1=0;
int vist[100003]={0};
int vist1[100003]={0};
struct jiedian{
	int data;
	struct jiedian *next;
};
struct biao{
	int data;
	struct jiedian *next=NULL;
}we[100003];
void dfs(int zhi){
	n1++;//计数，当输出是最后一个时，不用输出空格；
	if(n1!=n)
	cout<<zhi<<" ";
	else cout<<zhi;
	vist[zhi]=1;
	
	struct jiedian *sd=we[zhi].next;
	while(sd){
		if(!vist[sd->data])
		dfs(sd->data);
		else sd=sd->next;
	}
}
void bfs(int zhi){

	cout<<zhi<<" ";
	queue<int> m;
	m.push(zhi);
	struct jiedian *node=new jiedian();
	node=we[zhi].next;
	while(!m.empty()){
		int p=m.front();
		m.pop();
		node=we[p].next;
		for(;node;node=node->next){
			if(!vist1[node->data]){
				n1++;
				if(n1!=n)////计数，当输出是最后一个时，不用输出空格；
				cout<<node->data<<" ";
				else cout<<node->data;
				m.push(node->data);
				vist1[node->data]=1;
			}
		}
	}
}
int main(){
	
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
	   struct jiedian *duan=new jiedian();
	   duan->next=NULL;
	   //we[i].data=i;
	  // cout<<"132";
	   duan->data=y;
	   
	  struct jiedian * sd=we[x].next;
	   if(!sd){
	   duan->next=we[x].next;
		we[x].next=duan;  
	}
	else {
		while(sd->next){
			if(sd->data<y&&sd->next->data>=y) break;
			 sd=sd->next;
		}
		duan->next=sd->next;
		sd->next=duan; 
	}}
	dfs(1);
	n1=0;//重新初始化
	cout<<endl;
	bfs(1);
	return 0;
}