#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define min(a,b) ((a<b) ? (a) : (b))
#define max(a,b) ((a>b) ? (a) : (b))
#define pb push_back
#define mp make_pair
#define ll long long

using namespace std;

int cauta_binar(int*v, int a, int b, int x);
void fill(int x, int y);
void DFS(int x);
void BFS(int start);

int n, m, uz[1005], v[105], a[105][105];
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0,-1};
vector<int> L[1005];

int main()
{
	int i, x, y;

	cin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		cin >> x >> y;
		L[x].pb(y);
		L[y].pb(x);
	}
	DFS(1);
	cout << '\n';
	memset(uz, 0, sizeof(uz));
	BFS(1);
	return 0;
}

void DFS(int x)
{
	int i;

	uz[x] = 1;
	cout << x << ' ';
	for (i = 0; i < L[x].size(); i++)
		if (!uz[L[x][i]])
			DFS(L[x][i]);
}

void BFS(int start)
{
	int i, in, sf, aux, C[1005];

	in = sf = 0;
	C[sf++] = start;
	uz[start] = 1;
	while (in < sf)
	{
		aux = C[in++];
		cout << aux << ' ';
		for (i = 0; i < L[aux].size(); i++)
			if (!uz[L[aux][i]])
			{
				uz[L[aux][i]] = 1;
				C[sf++] = L[aux][i];
			}
	}
	cout << '\n';
}

void fill(int x, int y)
{
	int i, l9, c9;

	a[x][y] = 0;
	for (i = 0; i < 4; i++)
	{
		l9 = x + dx[i];
		c9 = y + dy[i];
		if (a[l9][c9] == 1)
			fill(l9, c9);
	}
}

int cauta_binar(int*v, int a, int b, int x)//cauta in intervalul [a,b] din vector prima aparitie a lui x si o returneaza
{										   //daca nu exista este returnata pozitia unde ar trebui inserat
	int in, sf, mij;

	in = a - 1;
	sf = b + 1;
	while (sf - in > 1)
	{
		mij = (in + sf) / 2;
		if (v[mij] < x)
			in = mij;
		else sf = mij;
	}
	return sf;
}