#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10,M = 1e6 + 10;
int n,m;
vector<int> g[N];
bool st[N];
void bfs(){
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int t = q.front();
		printf("%d ",t);
		q.pop();
		for(auto a:g[t]){
			if(st[a]) continue;
			st[a] = true;
			q.push(a);
		}
	}
}
void dfs(int u){
	for(auto a:g[u]){
		if(st[a]) continue;
		st[a] = true;
		printf("%d ",a);
		dfs(a);
	}
}
int main(){
	scanf("%d %d",&n,&m);
	while(m -- ){
		int a,b;
		scanf("%d %d",&a,&b);
		g[a].push_back(b);
	}
	for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
	printf("1 ");
	dfs(1);
	puts("");
	memset(st,false,sizeof(st));
	bfs();
    return 0;
}