#include<bits/stdc++.h>
using namespace std;
#define N 10001
//赶紧写完这题
//bfs广度优先搜索；递归函数实现
int graph[N][N] = { 0 };
int Dvisited[N] = { 0 };
int Bvisited[N] = { 0 };
queue<int>ss;
stack<int>aa;

void dfs(int v, int n) {
	std::stack<int> s;
	s.push(v);
	while (!s.empty()) {
		int curr = s.top();
		s.pop();
		if (!Dvisited[curr]) {
			Dvisited[curr] = true;
			std::cout << curr << " ";
			for (int i = n; i >= 1; --i) {
				if (!Dvisited[i] && graph[curr][i] != 0) {
					s.push(i);
				}
			}
		}
	}
}
void bfs(int v, int n) {
	Bvisited[v] = true;
	printf("%d ", v);
	ss.push(v);
	while (!ss.empty()) {
		v = ss.front();
		ss.pop();
		for (int i = 1; i <= n; i++) {
			if (!Bvisited[i] && graph[v][i] > 0) {
				Bvisited[i] = 1;
				printf("%d ", i);
				ss.push(i);
			}
		}
	}
}
int main() {
	int n, m;
	int i, j;

	cin >> n >> m;
	cin >> i >> j;
	int x = i;
	graph[i][j] = 1;
	for (int t = 1; t <= m; t++) {
		cin >> i >> j;
		graph[i][j] = 1;
	}
	//bfs广度优先搜索
	
				dfs(x, m);
				printf("\n");
				bfs(x, m);


			
			

		
		
	
}