# 1260번
from collections import deque

N, M, V = map(int,input().split())
graph = {}
for i in range(N):
    graph[i+1] = []

for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def DFS(root):
    visited = []
    stack = [root]

    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            graph[v].sort(reverse=True)
            for w in graph[v]:
                stack.append(w)
    return visited

def BFS(root):
    visited = [root]
    queue = deque([root])

    while queue:
        v = queue.popleft()
        graph[v].sort()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                queue.append(w)
    return visited

print(*DFS(V))
print(*BFS(V))