#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<cstdlib>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
const int N = 100000 + 10, M = 1000000 + 10;
int n, m;
bool vis[N];
vector<int> d[N];
void Bfs(int node) {
	bool vis[n + 10];
	memset(vis, false, sizeof(vis));
	queue<int> q;
	q.push(node);
	vis[node] = true;
	while (!q.empty()) {
		int u = q.front();
		for (unsigned i = 0; i < d[u].size(); i++) {
			int v = d[u][i];
			if (!vis[v]) {
				q.push(v);
				vis[v] = true;
			}
		}
		cout << u << " ";
		q.pop();
	}
}
void Dfs(int u) {
	cout << u << " ";
	for (unsigned i = 0; i < d[u].size(); i++) {
		int v = d[u][i];
		if (!vis[v]) {
			vis[v] = true;
			Dfs(v);
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		d[u].push_back(v);
	}
	Dfs(1);
	cout << endl;
	Bfs(1);
    return 0;
}