#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<bool>vis;
vector<vector<int> >adj;
void bfs(int u){
	queue<int>q;
	q.push(u);
	vis[u]=false;
	while(!q.empty()){
		int now=q.front();
		printf("%d ",now);
		q.pop();
		for(int nxt:adj[now]){
			if(!vis[nxt])continue;
			vis[nxt]=false;
			q.push(nxt);
		}
	}
}
void dfs(int u){
	if(vis[u])return;
	vis[u]=true;
	printf("%d ",u);
	for(int v:adj[u])dfs(v);
}
int main(){
	scanf("%d%d",&n,&m);
	vis.resize(n+1,false);
	adj.resize(n+1);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		adj[u].push_back(v);
	}
	for(vector<int> u:adj)
		sort(u.begin(),u.end());
	dfs(1);printf("\n");bfs(1);
	return 0;
}