##dfs bfs都已经用set自动排序了，不知道哪里错

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <ctype.h>
#include <ctime>
#include <stack>
#include <list>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1000005;
int n, m;
int h[N], e[N], ne[N], idx;
bool st[N];

void add(int x, int y)
{
	e[idx] = y;
	ne[idx] = h[x];
	h[x] = idx++;
}

void dfs(int u)
{
	st[u] = true;
	if (u != 1 && st[1] == true) cout << u << ' ';
	set<int > s;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!st[j])
		{
			st[j] = true;
			s.insert(j);
		}
	}
	for (set<int >::iterator iter = s.begin(); iter != s.end(); iter++)
	{
		dfs(*iter);
	}

}

bool arr[N];

void bfs(int k)
{
	queue<int > q;
	q.push(k);
	st[k] = true;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		set<int > s;
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (!st[j])
			{
				st[j] = true;
				s.insert(j);
			}
		}
		 
		for (set<int > ::iterator iter = s.begin(); iter != s.end(); iter++)
		{
			if (k == 1 || arr[k] == true)
			{
				arr[*iter] = true;
				cout << *iter << ' ';
			}
			q.push(*iter);
		}
	}
}

int d[N];


int main()
{
	memset(h, -1, sizeof(h));
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		d[y]++;
	}

	cout << 1 << ' ';
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			dfs(i);
		}
	}
	cout << endl;
	cout << 1 << ' ';
	for (int i = 0; i <= n; i++)
	{
		st[i] = false;
	}
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			bfs(i);
		}
	}

	return 0;
}