rt

#include <bits/stdc++.h>
using namespace std;
int dd[10005][10005],d[10005],db[10005][10005];
int n,e,u,v,s = 1;
void dfs(int x,int step)
{
	cout << x << " ";
	if (step == n)
		return ;
	for (int i = 1;i <= n;i++)
	{
		if (dd[x][i] == 1 && d[i] == 1)
		{
			dd[x][i] = dd[i][x] = d[i] = 0;
			dfs(i,step + 1);
		}
	}
}
int main()
{
	cin >> n >> e;
	for (int i = 1;i <= e;i++)
	{
		cin >> u >> v;
		dd[u][v] = dd[v][u] = db[u][v] = db[v][u] = 1;
	}
	for (int i = 1;i <= n;i++)
		d[i] = 1;
	d[1] = 0;
	dfs(1,1);
	for (int i = 1;i <= n;i++)
		d[i] = 1;
	d[1] = 0;
	queue<int> q;
	q.push(1);
	cout << endl << "1 ";
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (int i = 1;i <= n;i++)
		{
			if (db[now][i] == 1 && d[i] == 1)
			{
				q.push(i);
				db[i][now] = db[now][i] = d[i] = 0;
				cout << i << " ";
			}
		}
	}
	return 0;
}