n, m, v = map(int, input().split())

vertexs = {}
for i in range(1, n+1):
    vertexs[i] = set()

for _ in range(m):
    a, b = map(int, input().split())
    vertexs[a].add(b)
    vertexs[b].add(a)

check = [False]*(n+1)

def dfs(n):
    print(n,end=' ')
    check[n] = True
    for k in sorted(vertexs[n]):
        if not check[k]:
            dfs(k)

dfs(v)

print()
check = [False]*(n+1)
# 이미 간 곳 확인
queue = [v]
check[v] = True
print(v,end=' ')
while queue:
    v = queue.pop(0)
    for u in sorted(vertexs[v]):
        if not check[u] :
            print(u,end=' ')
            queue.append(u)
            check[u] = True