#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>

constexpr int MAXN = 1004;

bool D[MAXN][MAXN];
std::vector<int> E[MAXN];

int H[MAXN];
bool visited[MAXN];

int main() {
	int N, M, S;

	scanf("%d%d%d", &N, &M, &S);
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		D[x][y] = D[y][x] = true;
	}

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			if (D[i][j]) E[i].push_back(j);
		}
	}

	// DFS
	{
		std::vector<int> V;
		V.push_back(S);
		do {
			const int now = V.back();
			int &np = H[now];
			if (!visited[now]) {
				printf("%d ", now);
				visited[now] = true;
			}
			while (np < (int)E[now].size() && visited[E[now][np]]) ++np;
			if (np == (int)E[now].size()) V.pop_back();
			else V.push_back(E[now][np++]);
		} while (V.size());
	}

	puts("");
	std::fill(visited, &visited[N + 1], false);

	// BFS
	{
		std::deque<int> Q;
		Q.push_back(S);
		visited[S] = true;
		do {
			const int now = Q.front();
			Q.pop_front();
			printf("%d ", now);

			for (const int &e: E[now]) {
				if (visited[e]) continue;
				visited[e] = true;
				Q.push_back(e);
			}
		} while (Q.size());
	}
}