#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <iostream>
using namespace std;
typedef long long ll;
int N, M, V;
typedef struct Node {
char idx;
bool visited = false;
vector<int> vec;
// char vec_idx = 0;
}Node;
vector<Node> node_vec;
void input(void) {
cin >> N >> M >> V;
Node tmp;
tmp.idx = -1;
node_vec.push_back(tmp);
for (int i = 1; i <= N; i++)
{
Node new_node;
new_node.idx = i;
node_vec.push_back(new_node);
}
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
node_vec[a].vec.push_back(b);
node_vec[b].vec.push_back(a);
}
for (int i = 1; i <= N; i++)
sort(node_vec[i].vec.begin(), node_vec[i].vec.end());
}
void init(void)
{
for (int i = 1; i <= N; i++) {
node_vec[i].visited = false;
}
return;
}
void DFS(int v)
{
node_vec[v].visited = true;
cout << v << ' ';
for (int i = 0; i < node_vec[v].vec.size(); i++)
{
int node_num = node_vec[v].vec[i];
if (node_vec[node_num].visited == 0)
{
DFS(node_num);
}
}
return;
}
void BFS(int v)
{
queue<int> nq;
nq.push(v);
node_vec[v].visited = true;
while (!nq.empty())
{
int cur = nq.front();
nq.pop();
cout << cur << ' ';
for (int i = 0; i < node_vec[cur].vec.size(); i++)
{
int node_num = node_vec[cur].vec[i];
if (node_vec[node_num].visited == 0)
{
node_vec[node_num].visited = true;
nq.push(node_num);
}
}
}
}
void solve(void)
{
DFS(V);
init();
cout << endl;
BFS(V);
return;
}
int main()
{
input();
solve();
}