# Topic : Graph _ DFS와 BFS
#
# Python 3 : 128ms

from collections import deque
import queue
import sys

# dfs 구현
def dfs(graph, v, visited):
  visited[v] = True;
  result_dfs.append(v)

  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i , visited)

# bfs 구현
def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True
  result_bfs.append(start)

  while queue:
    v = queue.popleft()

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True
        result_bfs.append(i)

N, M, V = map(int,sys.stdin.readline().rstrip().split())

# 초기 graph 생성
graph = [[] for n in range(N+1)]

for _ in range(M):  
  a , b = map(int,sys.stdin.readline().rstrip().split())
  # 양방향 연결
  graph[a].append(b)
  graph[b].append(a)

# 정점 번호가 작은것 부터 먼저 방문
for g in graph: 
  g.sort()

# print("graph : ",graph)

# DFS
result_dfs = []

visited = [False] * (N+1)
dfs(graph,V,visited)
for rd in result_dfs:
  print(rd,end=" ")
print()

# BFS
result_bfs = []

visited = [False] * (N+1)
bfs(graph,V,visited)
for rb in result_bfs:
  print(rb,end=" ")