from collections import deque
n, m, v = [int(x) for x in input().split()]
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = [int(x) for x in input().split()]
graph[a].append(b)
graph[b].append(a)
for i in range(1,n+1):
graph[i].sort()
def bfs(c):
global vis
asw = []
q = deque()
q.append(c)
vis[c] = 1
while q:
c = q.popleft()
asw.append(c)
for a in graph[c]:
if vis[a] == 0:
q.append(a)
vis[a] = 1
return asw
def dfs(c):
global vis, asw
asw.append(c)
vis[c] = 1
for a in graph[c]:
if vis[a]==0:
dfs(a)
return asw
vis = [0]*(n+1)
asw = []
print(*dfs(v))
vis = [0]*(n+1)
print(*bfs(v))
