#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector <int> v[100001];
bool vb[100001];
int n,m;
void dfs(int x){
	cout << x << ' ';
	for(int i=0;i<v[x].size();i++){
		if(vb[v[x][i]])continue;
		vb[v[x][i]]=1;
		dfs(v[x][i]);
	}
}
void bfs(){
	queue <int> q;
	q.push(1);
	while(!q.empty()){
		int tmp=q.front();
		q.pop();
		cout << tmp << ' ';
		for(int i=0;i<v[tmp].size();i++)
			if(!vb[v[tmp][i]]){
				q.push(v[tmp][i]);
				vb[v[tmp][i]]=1;
			}
	}
}
signed main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin >> x >> y;
		v[x].push_back(y);
	}
	vb[1]=1;
	dfs(1);
	puts("");
	memset(vb,0,sizeof(vb));
	bfs();
}