#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue> 
using namespace std;
struct Edge {
	int a, b;
};
struct Node {
	int num;
	Node* next;
};
bool cmp(Edge a, Edge b) {
	if (a.a < b.a) {
		return true;
	}
	else if (a.a == b.a && a.b > b.b) {
		return true;
	}
	return false;
}
bool cmp1(Edge a, Edge b) {
	return !cmp(a, b);
}
int v[1000100];
int main() {
	ios::sync_with_stdio(0);
	memset(v, 0, sizeof(v));
	int n, m;
	cin >> n >> m;
	stack<int> s;
	queue<int> q, out1, out2;
	Node* headList = new Node[n + 1];
	Node** lastList = new Node * [n + 1];
	Edge* edge = new Edge[m];
	for (int i = 0; i <= n; i++) {
		lastList[i] = &headList[i];
		headList[i].num = -1;
		headList[i].next = NULL;
	}
	for (int i = 0; i < m; i++) {
		cin >> edge[i].a >> edge[i].b;
	}
	sort(edge, edge + m, cmp);
	for (int i = 0; i < m; i++) {
		lastList[edge[i].a]->next = new Node;
		lastList[edge[i].a] = lastList[edge[i].a]->next;
		lastList[edge[i].a]->next = NULL;
		lastList[edge[i].a]->num = edge[i].b;
	}
	Node* p;
	v[1] = 1;
	s.push(1);
	while (!s.empty()) {
		out1.push(s.top());
		v[s.top()] = 1;
		p = &headList[s.top()];
		s.pop();
		while (p->next) {
			p = p->next;
			if (!v[p->num]) {
				s.push(p->num);
			}
		}
	}
	while (!out1.empty()) {
		cout << out1.front();
		out1.pop();
		if (!out1.empty()) {
			cout << " ";
		}
	}
	cout << "\n";
	sort(edge, edge + m, cmp1);
	for (int i = 0; i <= n; i++) {
		lastList[i] = &headList[i];
		lastList[i]->next = NULL;
	}
	for (int i = 0; i < m; i++) {
		lastList[edge[i].a]->next = new Node;
		lastList[edge[i].a] = lastList[edge[i].a]->next;
		lastList[edge[i].a]->next = NULL;
		lastList[edge[i].a]->num = edge[i].b;
	}
	memset(v, 0, sizeof(v));
	v[1] = 1;
	q.push(1);
	while (!q.empty()) {
		p = &headList[q.front()];
		out2.push(q.front());
		q.pop();
		while (p->next) {
			p = p->next;
			if (!v[p->num]) {
				v[p->num] = 1;
				q.push(p->num);
			}
		}
	}
	while (!out2.empty()) {
		cout << out2.front();
		out2.pop();
		if (!out2.empty()) {
			cout << " ";
		}
	}
}