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

#define MAXN 100005
struct point{
	priority_queue<int,vector<int>,greater<int>> sons;
	bool dfs_vis=false;
	bool bfs_vis=false;
}tree[MAXN];

int n,m;

void dfs_print(int top){
	if(!tree[top].dfs_vis){
		printf("%d ",top);
		tree[top].dfs_vis=true;
	}else{
		return;
	}
	priority_queue<int,vector<int>,greater<int>> sons_copy=tree[top].sons;
	while(!sons_copy.empty()){
		dfs_print(sons_copy.top());
		sons_copy.pop();
	}
	return;
}

void bfs_print(int top){
	queue<int> bfs_q;
	bfs_q.push(top);
	while(!bfs_q.empty()){
		if(tree[bfs_q.front()].bfs_vis){
			bfs_q.pop();
			continue;	
		}
		printf("%d ",bfs_q.front());
		priority_queue<int,vector<int>,greater<int>> sons_copy=
									  tree[bfs_q.front()].sons;
		while(!sons_copy.empty()){
			bfs_q.push(sons_copy.top());
			sons_copy.pop();
		}
		tree[bfs_q.front()].bfs_vis=true;
		bfs_q.pop();
	}
	
	return;
}

int main(){
	scanf("%d",&n);
	scanf("%d",&m);
	int fa,so;
	for(int i=0;i<n;i++){
		scanf("%d %d",&fa,&so);
		tree[fa].sons.push(so);
	}
	dfs_print(1);
	printf("\n");
	bfs_print(1);
	printf("\n");
	
	return 0;
}