#include<bits/stdc++.h>
using namespace std;
struct ab {
	long long d, m;
}a[1000001];
bool cmp(ab a, ab b) {
	if (a.d == b.d)return a.m < b.m;
	return a.d < b.d;
}
long long n, k;
bool book[100001];
vector<long long> v[100001];
void DFS(int d) {
	book[d] = 1;
	cout << d << " ";
	for (auto i : v[d]) {
		if (!book[i]) {
			DFS(i);
		}
	}
}
void BFS(int k) {
	queue<int> q;
	q.push(k);
	book[k] = 1;
	memset(book, 0, sizeof(book));
	while (!q.empty()) {
		int ls = q.front();
		q.pop();
		cout << ls << " ";
		for (auto i : v[ls]) {
			if (!book[i]) {
				book[i] = 1;
				q.push(i);
			}
		}
	}
}
int main() {
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		cin >> a[i].d >> a[i].m;
	}
	sort(a + 1, a + k + 1, cmp);
	for (int i = 1; i <= k; i++) {
		v[a[i].d].push_back(a[i].m);
	}
	DFS(1);
	cout << "\n";
	BFS(1);
	return 0;
}