#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>
typedef struct edge
{
	int veradj;
	int cost;
	struct edge* link;
}edge;
typedef struct vertex
{
	int vername;
	edge* adjacent;
}vertex;
vertex head[100000];
vertex insert(vertex t, edge* item)
{
	edge* pre = t.adjacent, * p;
	if (t.adjacent == NULL) t.adjacent = item;
	else  if (t.vername<item->veradj && t.adjacent->veradj > item->veradj)
		item->link = t.adjacent, t.adjacent = item;
	else {
		p = pre->link;
		while (p != NULL)
		{
			if (pre->veradj < item->veradj && p->veradj > item->veradj)
			{
				item->link = p;
				pre->link = item;
				break;
			}
			pre = p;
			p = p->link;
		}
		if (p == NULL) pre->link = item;
	}
	return t;
}
int vis[100000];
int main()
{
	int m, n;
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= m; i++)
	{
		head[i].vername = i;
		head[i].adjacent = NULL;
	}
	while (n--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		edge* temp = malloc(sizeof(edge));
		temp->veradj = b;
		temp->link = NULL;
		head[a] = insert(head[a], temp);
	}
	void bfs(vertex*, int);
	void dfs(vertex*, int);
	dfs(head, 1);
	printf("\n");
	for (int i = 1; i <= m; i++)
		vis[i] = 0;
	bfs(head, 1);
	return 0;
}
void dfs(vertex* t, int v)
{
	vis[v] = 1;
	printf("%d ", v);
	edge* p = t[v].adjacent;
	while (p != NULL)
	{
		int k = p->veradj;
		if (vis[k] == 0)
		{
			dfs(t, k);
		}
		p = p->link;
	}
}
void bfs(vertex* t, int v)
{
	int front, rear;
	front = rear = 0;
	int queue[100000];
	queue[rear++] = v;
	while (front != rear)
	{
		printf("%d ", queue[front]);
		edge* p = t[queue[front++]].adjacent;
		while (p != NULL)
		{
			int k = p->veradj;
			if (vis[k] == 0) queue[rear++] = k, vis[k] = 1;
			p = p->link;
		}
	}