//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 100005
using namespace std;
vector<int> p[MAXN];
queue<int> q;//创建队列(BFS 
bool u[MAXN];//DFS所使用的标记数组 
bool u2[MAXN];//BFS所使用的标记数组 
void solve(int x){
	cout<<x<<" ";//开始输出
	for(int i= 0,size = p[x].size();i < size;i++){
		if(!u[p[x][i]]){
			u[p[x][i]] = true;
			solve(p[x][i]);
		}
	} 
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 0;i < m;i++){
		int x,y;
		cin>>x>>y;
		p[x].push_back(y);//邻接表 
	}
	
	
	//DFS
	u[1] = true;
	solve(1);
	
	cout<<endl;
	
	//BFS
	q.push(1);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		cout<<x<<" ";
		for(int i = 0,size2 = p[x].size();i <size2;i++){
			if(!u2[p[x][i]]){
				u2[p[x][i]] = true;
				q.push(p[x][i]);
			}
		}
	}
	return 0;
}