#include <iostream>
#include <vector>

const int MAX = 1001;

class Staque {
private:
	int staque[MAX] = {}, top = 1, front = 1;
public:
	bool empty()
	{
		if (top == front)
			return true;
		else
			return false;
	}
	bool full()
	{
		if ((top + 1) % MAX == front)
			return true;
		else
			return false;
	}
	void push(int a)
	{
		if (full()) return;
		if (top == 0)
			++top;
		staque[(top++)%MAX] = a;
	}
	int pop()
	{
		if (empty())
			return 0;
		return staque[(--top)%MAX];
	}
	int deStq()
	{
		if (empty())
			return 0;
		return staque[(front++)%MAX];
	}
};

class Graph
{
private:
	std::vector<int> vertex[MAX];
public:
	void linkVertex(int a, int b) 
	{
		int left = 0, right = vertex[a].size() - 1;
		while (right >= left) {
			if (b > vertex[a].at((left + right) / 2))
				left = (left + right) / 2 + 1;
			else if (b < vertex[a].at((left + right) / 2))
				right = (left + right) / 2 - 1;
			else
				return;
		}
		vertex[a].insert(vertex[a].begin() + left, b);
	}
	void insertEdge(int a, int b)
	{
		if (a == b)
			return;
		linkVertex(a, b);
		linkVertex(b, a);
	}
	void DFS(int v)
	{
		Staque staque;
		int visited[MAX] = {}, w;
		visited[v] = 1;
		printf("%d ", v);
		staque.push(v);
		while (!staque.empty()) {
			w = 0;
			while (w < vertex[v].size() && visited[vertex[v].at(w)] == 1) w++;
			if (w < vertex[v].size()) {
				w = vertex[v].at(w);
				visited[w] = 1;
				printf("%d ", w);
				staque.push(w);
				v = w;
			}
			else v = staque.pop();
		}
	}
	void BFS(int v)
	{
		Staque staque;
		int visited[MAX] = {}, temp;
		visited[v] = 1;
		printf("%d ", v);
		staque.push(v);
		while (!staque.empty()) {
			v = staque.deStq();
			for (int w = 0; w < vertex[v].size(); w++) {
				temp = vertex[v].at(w);
				if (visited[temp] == 0) {
					visited[temp] = 1;
					printf("%d ", temp);
					staque.push(temp);
				}
			}
		}
	}
};

int main(void)
{
	Graph graph;
	int n, m, v, v1, v2;
	
	scanf("%d %d %d", &n, &m, &v);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &v1, &v2);
		graph.insertEdge(v1, v2);
	}
	graph.DFS(v);
	printf("\n");
	graph.BFS(v);
}
/*
Input example
7 6 1
1 4
1 3
1 2
4 6
4 5
2 7

Output example
1 2 7 3 4 5 6
1 2 3 4 7 5 6
*/