#include<iostream>
using namespace std;
struct cell
{
	int x;
	cell* link;
};
cell* p[100001],*e[100001];
int v[100001],vv[100001];
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		p[i] = (struct cell*)malloc(sizeof(struct cell));
		p[i]->x = i;
		p[i]->link = NULL;
		e[i] = (struct cell*)malloc(sizeof(struct cell));
		e[i]->x = i;
		e[i]->link = NULL;
		vv[i] = 0;
		v[i] = 0;
	}
	int x, y;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		//c[x]++;
		if (p[x]->link == NULL)
		{
			cell* q = (struct cell*)malloc(sizeof(struct cell));
			q->x = y;
			q->link = NULL;
			p[x]->link = q;
		}
		else
		{
			cell* q = (struct cell*)malloc(sizeof(struct cell));
			q->x = y;
			q->link = NULL;
			if (p[x]->link->x >= q->x)
			{
				q->link = p[x]->link;
				p[x]->link = q;
			}
			else
			{
				cell* t = p[x]->link;
				cell* t1 = t->link;
				while (t1 != NULL)
				{
					if (t1->x >= q->x)
					{
						q->link = t1;
						t->link = q;
						break;
					}
					t = t1;
					t1 = t1->link;
				}
				if (t1 == NULL)
				{
					t->link = q;
				}
			}
		}
		if (e[x]->link == NULL)
		{
			cell* q = (struct cell*)malloc(sizeof(struct cell));
			q->x = y;
			q->link = NULL;
			e[x]->link = q;
		}
		else
		{
			cell* q = (struct cell*)malloc(sizeof(struct cell));
			q->x = y;
			q->link = NULL;
			if (e[x]->link->x <= q->x)
			{
				q->link = e[x]->link;
				e[x]->link = q;
			}
			else
			{
				cell* t = e[x]->link;
				cell* t1 = t->link;
				while (t1 != NULL)
				{
					if (t1->x <= q->x)
					{
						q->link = t1;
						t->link = q;
						break;
					}
					t = t1;
					t1 = t1->link;
				}
				if (t1 == NULL)
				{
					t->link = q;
				}
			}
		}
	}
	int q[100001];
	int top = 0;
	int fron = 0;
	q[top++] = 1;
	//v[1] = 1;
	//DFS
	while(top>0)
	{
		int t = q[top-1];
		cout<<t<<" ";
		v[t] = 1;
		top--;
		cell* o = e[t]->link;
		while (o != NULL)
		{
			if (v[o->x] != 1)
			{
				q[top++] = o->x;
			}
			o = o->link;
		}
	}
	
	//BFS
	top = 0;
	fron = 0;
	q[top++] = 1;
	cout << endl << q[fron] << " ";
	v[1] = 1;
	while (top > fron)
	{
		int t = q[fron];
		//cout << t << " ";
		//v[t] = 1;
		fron++;
		cell* o = p[t]->link;
		while (o != NULL)
		{
			if (vv[o->x] != 1)
			{
				cout << o->x << " ";
				vv[o->x] = 1;
				q[top++] = o->x;
			}
			o = o->link;
		}
		
	}
	return 0;
}