#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,m,tot,head[N],vis[N];
int cnt,ans[N];
struct node {int to,next;}e[M];
struct Edge{int u,v;}edge[M];

void add(int u,int v){e[++tot]={v,head[u]};head[u]=tot;}

bool cmp(Edge x,Edge y){
	if(x.u!=y.u)return x.u<y.u;
	else return x.v>y.v;
}

void dfs(int s){
	if(vis[s])return;
	vis[s]=1; ans[++cnt]=s; //建议在自己的分支里去做自己的事情，不要帮别人做
	for(int i=head[s];i;i=e[i].next){
		int v=e[i].to;
		dfs(v);
	}
}

void bfs(int s){
	memset(vis,0,sizeof(vis));
	cnt=0;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		if(vis[u]) continue;
		vis[u]=1; ans[++cnt]=u;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			q.push(v);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d %d",&edge[i].u,&edge[i].v);
	}
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++) add(edge[i].u,edge[i].v);
	dfs(1);
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';cout<<'\n';
	bfs(1);
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';cout<<'\n';
}