#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v;
	
};
vector<int> e[114514];
vector<edge> s;
bool visited1[14514]={0};visited2[114514]={0};
bool cmp(edge x,edge y){
	if(x.v==y.v)
	return x.u<y.u;
	else {return x.v<y.v;}
	
}
void dfs(int x){
	visited1[x]=1;
	cout<<x<<" ";
	for(int i=0;i<e[x].size();i++){
		int point=s[e[x][i]].v;
		if(!visited1[point]){
			dfs(point);
			
		}
		//TODO
	}
}
void bfs(int x){
	queue<int> q;
	q.push(x);
	cout<<x<<" ";
	visited2[x]=1;
	while(!q.empty()){
		int fron=q.front();
		for(int i=0;i<e[fron].size();i++){
			int point =s[e[fron][i]].v;
			if(!visited2[point]){
				q.push(point);
				cout<<point<<" ";
				visited2[point]=1;
				
				//TODO
			}
			//TODO
			q.pop();
		}
		
		//TODO
	}
}
int main(){
	int a,b;
	cin>>a>>b;
	for(int i=0;i<b;i++){
		int uu,vv;
		cin>>uu>>vv;
		s.push_back((edge){uu,vv});
	}
	sort(s.begin(),s.end(),cmp);
	for(int i=0;i<b;i++)
	e[s[i].u].push_back(i);
	dfs(1);
	cout<<endl;
	bfs(1); 
}

CE了啊啊啊啊啊，不知道问题出在哪里...............