#include<iostream>
#include<cstring>

using namespace std;

int graph[10001][10001];
int visited[10001];
int path[10001];
int cnt = -1;
void dfs(int x,int n)
{
	cnt++;
	path[cnt] = x;
	visited[x] = 1;
	if (cnt == n) return;
	for (int i = 1; i <= n; i++)
	{
		if (graph[x][i] == 1 && visited[i] == 0)
		{
			dfs(i, n);
		}
	}

}
void bfs(int a, int n)
{
	int qu[10001];
	int front = -1, rear = -1, x;
	rear++;
	qu[rear] = a;
	visited[a] = 1;
	while (front != rear)
	{
		front++;
		x = qu[front];
		for (int i = 1; i <= n; i++)
		{
			if (visited[i] == 0 && graph[x][i] == 1)
			{
				rear++;
				qu[rear] = i;
				visited[i] = 1;
			}
		}
	}
	for (int k = 0; k <= front; k++)
	{
		cout << qu[k] << " ";
	}
}
int main()
{
	int n, e;
	cin >> n >> e;
	int x, y;
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < e; i++)
	{
		cin >> x >> y;
		graph[x][y] = 1;
	}
	dfs(1, n);
	for (int i = 0; i <= cnt; i++)
	{
		cout << path[i]<<" ";
	}
	cout << endl;
	memset(visited, 0, sizeof(visited));
	bfs(1, n);
	return 0;
}