#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define pii pair<int,int>
#define debug printf("++ ++");
#define fi first
#define second se
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5;
int n, m, num;
int vis[N + 5];
vector<int>G[N + 5];
void dfs(int now) {
	vis[now] = 1;//标记now号节点（起始now==1）
	if (now != 1) printf(" ");
	printf("%d", now);
	sort(G[now].begin(), G[now].end());//对当前节点指向边排序
	for (auto to : G[now]) {
		if (vis[to]) continue;
		dfs(to);
	}
}
void bfs(int root) {
	memset(vis, 0, sizeof vis);
	priority_queue<pii, vector<pii>, greater<pii>>pq;//必须重载比较函数（重载优先队列，按照优先按照pii第一个数据从小到大排序，再按照pii.second从小到大排）
	pq.push({0, root});
	vis[root] = 1;
	while (!pq.empty()) {
		auto [dis, from] = pq.top();//取出队首素
		pq.pop();
		if (from != 1) printf(" ");
		printf("%d", from);
		for (auto to : G[from]) {
			if (vis[to]) continue;
			vis[to] = 1;
			pq.push({dis + 1, to});放入队列
		}
	}
}
int main() {
	int u, v;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u, &v);//单向存图
		G[u].push_back(v);
	}
	dfs(1);
	printf("\n");
	bfs(1);
	return 0;
}

//呜呜呜