import sys
input = sys.stdin.readline
N,M,V = map(int, input().split())
graph = [[] for _ in range(N+1)]
for m in range(M):
u,v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
for n in range(1, N+1):
graph[n].sort()
# DFS
visit = [0 for _ in range(N+1)]
def dfs(node, G, visited):
visited[node] = 1
result = [node]
for child in G[node]:
if visited[child] == 0:
result += dfs(child, G, visited)
return result
dfs_result = dfs(V, graph, visit)
print(*dfs_result, sep=' ')
# BFS
queue = []
bfs_result = []
visit = [0 for _ in range(N+1)]
visit[V] = 1
queue.append(V)
while len(queue):
node = queue.pop(0)
bfs_result.append(node)
for child in graph[node]:
if visit[child] == 0:
visit[child] = 1
queue.append(child)
print(*bfs_result, sep=' ')