#include<bits/stdc++.h>
using namespace std;

vector<int> g[123456];

int n,m; 
int a,b;

bool vis[123456]={0};


dfs(int x){
	if(!vis[x]){
		cout<<x<<" ";
		vis[x]=1;
		for(int i=0;i<g[x].size();i++){
			dfs(g[x][i]);
		}
	}
}

queue<int> q;
int x;

bfs(){
	while(!q.empty()){
		x=q.front();
		q.pop();
		if(!vis[x]){
			cout<<x<<" ";
			vis[x]=1;
			for(int i=0;i<g[x].size();i++){
				if(!vis[g[x][i]]){
					q.push(g[x][i]);
				}
			}
		}
	}
}


int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		g[a].push_back(b); 
	}
	
	dfs(1);
	cout<<endl;
	
	memset(vis,0,sizeof(vis));
	q.push(1);
	bfs();
	
	
	
	return 0;
}