#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
const int maxn = 1e6 + 10;

struct node {
	int u, v;
};

struct Edge {
	int v, next;
};

bool vis[N];
int n, m, cnt;
int head[N]; 
Edge e[maxn];
node nd[maxn];

bool cmp(node a, node b) {
	if (a.u != b.u)
		return a.u < b.u;
	else
		return a.v > b.v;
}

void add(int u, int v) {
	e[++cnt].v = v;
	e[cnt].next = head[u];
	head[u] = cnt++;
}

void dfs(int u) {
	vis[u] = 1;
	cout << u << " ";
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (!vis[v])
			dfs(v); 
	} 
}

void bfs(int u) {
	vis[u] = 1;
	queue<int> q;
	q.push(u);
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		cout << t << " ";
		for (int i = head[t]; i; i = e[i].next) {
			int v = e[i].v;
			if (!vis[v]) {
				vis[v] = 1;
				q.push(v);
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; ++i) scanf("%d %d", &nd[i].u, &nd[i].v);
	sort(nd, nd + n, cmp);
	for (int i = 0; i < m; ++i) add(nd[i].u, nd[i].v);
	dfs(1);
	cout << endl;
	memset(vis, 0, sizeof(vis));
	bfs(1);
	return 0;
}