#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1000020;
int h[N], e[N * 2], ne[N * 2], idx;
int n, m;
int vs1[N];

struct sb
{
	int a, b;
}arr[N*2];

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


bool cmp(sb x, sb y)
{
	if (x.a == y.a) return x.b >= y.b;
	return  x.a > y.a;
}

void dfs(int u)
{
	printf("%d ", u);
	vs1[u] = 1;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!vs1[j])dfs(j);	
	}
}

void bfs(int u)
{
	queue<int>q;
	vs1[u] = 1;
	q.push(u);
	printf("%d ", u);
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		for (int j = h[t]; j != -1; j = ne[j])
		{
			int k = e[j];
			if (!vs1[k])
			{
				printf("%d ", k);
				q.push(k);
				vs1[k] = 1;				
			}
		}
		
	}
}

int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;
	for (int i = 0; i < m; i++)scanf("%d %d", &arr[i].a, &arr[i].b);
	sort(arr, arr + n, cmp);
	for (int i = 0; i < m; i++)
		add(arr[i].a, arr[i].b);
	dfs(1);
	cout << endl;
	memset(vs1, 0, sizeof vs1);
	bfs(1);
	return 0; 
}