#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int n, m;
bool look[100001];
int ltp, lk[100001];
struct node{int nxt, y;}e[100001];

struct edge{int x, y;}l[1000001];

bool cmp(edge a, edge b) {
	if (a.x == b.x) return a.y > b.y;
	return a.x > b.x;
}

void dfs(int a) {
	if (look[a]) return ;
	for (int i = lk[a]; i; i = e[i].nxt) {
		if (look[e[i].y]) continue;
		printf("%d ", e[i].y);
		dfs(e[i].y);
		look[e[i].y] = 1;
	}
}

void bfs(int a) {
	queue < int > q;
	q.push(1); look[1] = 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = lk[x]; i; i = e[i].nxt) {
			if (look[e[i].y]) continue;
			q.push(e[i].y);
			look[e[i].y] = 1;
			printf("%d ", e[i].y);
		}
	}
}

void ist(int x, int y) {
	e[++ltp] = (node){lk[x], y}; lk[x] = ltp;
}

int main() {

	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++ i) {
		scanf("%d%d", &l[i].x, &l[i].y);
	}

	sort(l, l + m, cmp);
	
	for (int i = 0; i < m; ++ i) {
		ist(l[i].x, l[i].y);
	}
	
	printf("1 ");
	dfs(1);

	memset(look, 0, sizeof(look));

	printf("\n1 ");
	bfs(1);

	return 0;
}