#include <stdio.h>
#define E 1001
int metrix[E][E];
int visits[E * E];
int q[E];
int front = -1, rear = -1;
void initBfs () {
for (int i = 0; i < E * E; i++) {
visits[i] = 0;
}
}
void DFS (int V, int N) {
visits[V] = 1;
printf("%d ", V);
for (int i = 1; i <= N; i++) {
if (!visits[i] && metrix[V][i]) {
DFS(i, N);
}
}
}
void BFS (int V, int N) {
rear++;
q[rear] = V;
visits[V] = 1;
printf("%d ", V);
while (front < rear) {
front++;
int v = q[front];
for (int i = 1; i <= N; i++) {
if (!visits[i] && metrix[v][i]) {
printf("%d ", i);
rear++;
q[rear] = i;
visits[i] = 1;
}
}
}
}
int main(void) {
int N = 0;
int M = 0;
int V = 0;
scanf("%d %d %d", &N, &M, &V);
for (int i = 0; i < M; i++) {
int firstV = 0;
int secondV = 0;
scanf("%d %d", &firstV, &secondV);
metrix[firstV][secondV] = 1;
metrix[secondV][firstV] = 1;
}
DFS(V, N);
printf("\n");
initBfs();
BFS(V, N);
printf("\n");
return 0;
}
