from collections import deque
import sys
input = sys.stdin.readline

N,M,V = map(int,input().split())

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

for i in graph:
    i.sort()

visited = [False]*(N+1)
DFSvisits = [V]
def dfs(v):
    for i in graph[v]:
        if not visited[i]:
            visited[i]=True
            DFSvisits.append(i)
            dfs(i)
visited[V]=True
dfs(V)

visited = [False]*(N+1)
BFSvisits = [V]
def bfs(v):
    queue = deque([v])
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if not visited[i]:
                visited[i]=True
                BFSvisits.append(i)
                queue.append(i)
visited[V]=True
bfs(V)

print(*DFSvisits)
print(*BFSvisits)