def dfs(v):
visited1[v]=True
print(v,end=' ')
for i in range(1,n+1):
if graph[v][i]==True and visited1[i]==False:
dfs(i)
def bfs(v):
visited2[v]=True
queue=[v]
while queue:
V=queue.pop(0)
print(V,end=' ')
for i in range(1,n+1):
if graph[V][i]==True and visited2[i]==False:
queue.append(i)
visited2[i]=True
n,m,v=map(int,input().split())
graph=[[False]*(n+1) for _ in range(n+1)]
visited1=[False for _ in range(n+1)]
visited2=[False for _ in range(n+1)]
for i in range(1,m+1):
x,y=map(int,input().split())
graph[x][y]=True
graph[y][x]=True
dfs(v)
print()
bfs(v)