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

vector<int> v[1000005];

bool f[1000005];
void dfs(int id){
	cout << id << " ";
	for(int i = 0; i < v[id].size(); i++){
		if(!f[v[id][i]]){
			f[v[id][i]] = true;
			dfs(v[id][i]);
		}
	}
}


deque<int> q;
void bfs(){
	q.push_back(1);
	while(!q.empty()){
		int t = q.front();
		cout << t << " "; 
		q.pop_front();
		for(int i = 0; i < v[t].size(); i++){
			if(!f[v[t][i]]){
				f[v[t][i]] = true;
				q.push_back(v[t][i]);
			}
		}	
	}
	
}

int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
	}
	for(int i = 1; i <= n; i++){
		sort(v[i].begin(), v[i].end());
	}
	
	dfs(1);
	cout << endl;
	f[1] = true;
	memset(f, false, sizeof(f));
	f[1] = true;
	bfs(); 
	return 0;
}