#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int>G[114514];
int vis1[114514];
int vis2[114514];
void dfs()
{
	stack<int>st;
	st.push(1);
	vis1[1] = 1;
	while (st.size())
	{
		int u = st.top();
		st.pop();
		cout << u << ' ';
		for (int i = G[u].size() - 1; i >= 0; --i)
		{
			if (!vis1[G[u][i]])st.push(G[u][i]), vis1[G[u][i]] = 1;
		}

	}
}

void bfs()
{
	queue<int>q;
	q.push(1);
	vis2[1] = 1;
	while (q.size())
	{
		int u = q.front();
		q.pop();
		cout << u << ' ';
		for (int i = 0; i < G[u].size(); ++ i)
		{
			if (!vis2[G[u][i]])q.push(G[u][i]), vis2[G[u][i]] = 1;
		}

	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
	}
	for (int i = 0; i < n; ++i)
	{
		sort(G[i].begin(), G[i].end());
	}
	dfs();
	cout << endl;
	bfs();
}