#include<iostream>
#include<algorithm>
#include<queue> 

#define x first
#define y second
typedef std::pair<int,int> pii;

bool cmp(pii p1,pii p2){
	if(p1.x==p2.x)return p1.y>=p2.y;
	return p1.x<p2.x;
}
const int N=100010,M=10*N;

int n,m;
int h[N],e[M],ne[N],idx;
pii arr[M];
bool st[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
	std::cout<<u<<" ";
	st[u]=true;
	for(int i=h[u];i!=-1;i=ne[i]){
		int j =e[i];
		if(!st[j])dfs(j);
	}
}
void bfs(int u){
	std::queue<int> q; 
	q.push(u);
	std::cout<<u<<" ";
	st[u]=false;
	while(!q.empty()){
		int f=q.front();
		q.pop();
		for(int i=h[f];i!=-1;i=ne[i]){
			int j=e[i];
			if(st[j]){
				q.push(j);
				std::cout<<j<<" ";
				st[j]=false;
			}
		}
	}
}

void solve(){
	int n,m;
	std::cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++){
		std::cin>>arr[i].x>>arr[i].y;
	}
	std::sort(arr+1,arr+1+m,cmp);
	for(int i=1;i<=m;i++)add(arr[i].x,arr[i].y);
	dfs(1);
	std::cout<<"\n";
	bfs(1);
	std::cout<<"\n";

}
int main(){
	int t=1;
	std::fill(h,h+N,-1);
//	std::cin>>t;
	while(t--)solve();


	return 0;

}