AC

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector<int> p[MAXN];

int vis[MAXN] = {0};
vector<int> res;


void dfs(int x) {
	vis[x] = 1;
	res.push_back(x);

	for (auto next : p[x]) {
		if (!vis[next]) {
			dfs(next);
		}
	}
}


void bfs(int x) {
	queue<int> q;
	q.push(x);
	vis[x] = 1;
	while (!q.empty()) {
		int t = q.front();
		res.push_back(t);
		q.pop();
		for (auto next : p[t]) {
			if (!vis[next]) {
				vis[next] = 1;
				q.push(next);
			}
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	while (m--) {
		int x, y;
		cin >> x >> y;
		p[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) {
		sort(p[i].begin(), p[i].end());
	}

	dfs(1);
	for (auto ans : res) {
		cout << ans << " ";
	}
	cout << endl;

	memset(vis, 0, sizeof(vis));
	res.clear();

	bfs(1);
	for (auto ans : res) {
		cout << ans << " ";
	}
	cout << endl;

	return 0;
}