#include
#include
#include
#include
using namespace std;
int n, m, x, y;
int q[1111], head = 1, rear = 1;
int vis[11111], G[111][111];
int q1[1111], head1 = 1, rear1 = 1;
int vis1[11111], G1[111][111];
void dfs(int k) {
/*
if (k > n)
return;
for (int i = 1; i <= n; i++) {
if (vis1[i] != 1 && G1[k][i] == 1) {
cout << i << " ";
vis1[i] = 1;
dfs(i);
}
}
*/
}
void bfs() {
q[rear++] = 1;
vis[1] = 1;
cout << 1 << " ";
while (head < rear) {
int tmp = q[head];
for (int i = 1; i <= n; i++) {
if (vis[i] == 0 && G[tmp][i] == 1) {
q[rear++] = i;
vis[i] = 1;
cout << i << " ";
}
}
head++;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
G[x][y] = 1;
G[y][x] = 1;
G1[x][y] = 1;
G1[y][x] = 1;
}
cout << 1 << " ";
vis1[1] = 1;
dfs(1);
cout << endl;
bfs();
return 0;
}