#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define QC 100001

struct node{
	int * next;
	int capcity;
	int size;
} A[100001];
 
int comp(const void * p1, const void * p2)
{
	return *(const int *)p1 - *(const int *)p2;
}

void add(int a, int b)
{
	if (A[a].size <= A[a].capcity)
	{
		A[a].next = realloc(A[a].next, A[a].capcity += 100);
	}
	A[a].next[A[a].size++] = b;
	return ;
}

void SortNext(int i)
{
	qsort(A[i].next, A[i].size, sizeof(int), comp);
}

bool DKnown[100001] = {[1] = true};
void DFS(int i)
{
	DKnown[i] = true;
	printf("%d ", i);
	for (int j = 0; j < A[i].size; j++)
	{
		if (!DKnown[A[i].next[j]])
			DFS(A[i].next[j]);
	}
	return ;
}

int Queue[QC] = {1}, front = 0, rear = 0, Qsize = 1;
bool BKnown[100001] = {[1] = true};
void BFS(void)
{
	while (Qsize)
	{
		int i = Queue[front];
		printf("%d ", i);
		front = (front + 1) % QC;
		Qsize--;
		for (int j = 0; j < A[i].size; j++)
		{
			int t = A[i].next[j];
			if (!BKnown[t])
			{
				BKnown[t] = true;
				rear = (rear + 1) % QC;
				Queue[rear] = t;
				Qsize++;
			}
		}
	}
}


int main(void)
{
	int n, m;
	scanf("%d%d", &n, &m);
	while (m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
	}
	for (int i = 0; i < n; i++)
	{
		SortNext(i);
	}
	DFS(1);
	putchar('\n');
	BFS();
	return 0;
}