#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

vector<int> edge[N];
bool st[N];
int n,m;
int q[N], front, rear;//队列

void dfs(int u)
{
	st[u] = true;

	for (int it : edge[u])
	{
		if (!st[it])
		{
			st[it] = true;
			cout << it << ' ';
			dfs(it);
		}
	}
}
void bfs(int u)
{
	q[front] = u;
	front = 0, rear = 0;
	st[u] = true;

	while (front <= rear)
	{
		int t = q[front];
		++front;
		st[t] = true;

		for (int it : edge[t])
		{
			if (!st[it])
			{
				cout << it << ' ';
				q[++rear] = it;
				st[it] = true;
			}
		}
	}
}
int main()
{
	cin >> n >> m;

	while (m--)
	{
		int x, y;
		cin >> x >> y;

		edge[x].push_back(y);
		//edge[y].push_back(x);
	}

	for (int i = 1;i <= n;++i) sort(edge[i].begin(), edge[i].end());

	for (int i = 1;i <= n;++i)
	{
		if (!st[i]) cout<<i<<' ',dfs(i);
	}

	cout << endl;

	

	memset(st, false, sizeof st);

	for (int i = 1;i <= n;++i)
	{
		if (!st[i]) cout<<i<<' ', bfs(i);
	}

	return 0;
}