#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v;
}e[1000005];
int head[1000005],ver[1000005],nextn[1000005],total=0;
bool visited[1000005];
queue<int> a;
int n,m;
bool cmp(edge a,edge b){
	if(a.u==b.u) return a.v>b.v;
	return a.u<b.u;
}
void add(int x,int y){
	ver[++total]=y;
	nextn[total]=head[x];
	head[x]=total;
}
void dfs(int x){
	visited[x]=true;
	cout<<x<<' ';
	for(int i=head[x];i;i=nextn[i]){
		if(!visited[ver[i]]) dfs(ver[i]);
	}
	return ;
}
void bfs(int x){
	visited[x]=true;
	a.push(x);
	while(!a.empty()){
		for(int i=head[a.front()];i;i=nextn[i]){
			if(!visited[ver[i]]){
				a.push(ver[i]);
				visited[ver[i]]=true;
			}	
		}
		cout<<a.front()<<' ';
		a.pop();
	}
	return ;
}
int main(){
	memset(visited,0,sizeof(visited));
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>e[i].u>>e[i]	.v;
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=m;i++) add(e[i].u,e[i].v);
	dfs(1);
	cout<<endl;
	memset(visited,0,sizeof(visited));
	bfs(1);
	return 0;
}