#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int queue[1001];
int N;
int M;
void DFS(int start, int** arr, int* visited)
{
visited[start] = 1;
printf("%d ", start);
int idx;
idx = 1;
while (idx <= N)
{
if (arr[start][idx] == 1 && visited[idx] == 0)
{
DFS(idx, arr, visited);
}
idx++;
}
}
void BFS(int start, int** arr, int* visited)
{
visited[start] = 1;
printf("%d ", start);
int idx;
int front;
int rear;
int pop;
front = 0;
rear = 1;
queue[front] = start;
while (front < rear)
{
pop = queue[front];
idx = 0;
while (idx <= N)
{
if (arr[pop][idx] == 1 && visited[idx] == 0)
{
visited[idx] = 1;
printf("%d ", idx);
queue[rear] = idx;
rear++;
}
idx++;
}
front++;
}
}
int main()
{
int V;
int idx;
int n;
int v;
scanf("%d %d %d", &N, &M, &V);
int ** arr = (int **) malloc(sizeof(int)*(N+1));
idx = 0;
while (idx <= N)
{
arr[idx] = (int *)malloc(sizeof(int*)*(N+1));
int idx2 = 1;
while (idx2 <= N)
{
arr[idx][idx2] = 0;
idx2++;
}
idx++;
}
int * visited = (int*) malloc(sizeof(int)*(N+1));
memset(visited, 0, sizeof(int)*(N+1));
idx = 1;
while (idx <= M)
{
scanf("%d %d", &n, &v);
arr[n][v] = 1;
arr[v][n] = 1;
idx++;
}
DFS(V, arr, visited);
memset(visited, 0, sizeof(int)*(N+1));
printf("\n");
BFS(V, arr, visited);
free(arr);
free(visited);
}