#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1000100, M = 1000010;
PII path[M];
int e[M], ne[M], h[N], idx, n, m, st[N], d[N];
bool cmp(PII a, PII b) {
	if(a.first < b.first) {
		return a > b;
	}else if(a.first == b.first) {
		if(a.second > b.second) return a > b;
		else return b < a;
	}else {
		return b > a;
	}
}
void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dfs(int u) {
	st[u] = 1;
	printf("%d ", u);
	for(int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if(!st[j]) dfs(j);
	}
}
void bfs() {
	memset(st, 0, sizeof(st));
	queue<int> q;
	st[1] = 1;
	q.push(1);
	while(!q.empty()) {
		int t = q.front();
		printf("%d ", t);
		q.pop();
		for(int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if(!st[j]) {
				q.push(j);
				st[j] = 1;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	memset(h, -1, sizeof(h));
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		d[b]++;
		path[i] = {a, b};
	}
	sort(path, path + m, cmp);
	for(PII x : path) {
		add(x.first, x.second);
	}
	dfs(1);
	printf("\n");
	bfs();
	return 0;
}