def dfs(arr, now, visited) :
    if not visited[now] :
        print(now, end = " ")
        visited[now] = True
    for next in arr[now] :
        if not visited[next] :
            dfs(arr, next, visited)

def bfs(arr, start, visited) :
        from collections import deque
        queue = deque([start])
        visited[start] = True

        while len(queue) != 0:
            v = queue.popleft()
            print(v, end = " ")
            for n in arr[v] :
                if not visited[n] :
                    queue.append(n)
                    visited[n] = True

N, M, V = map(int, input().split())
arr = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for _ in range(M) :
    n, m = map(int,input().split())
    arr[n].append(m)
    arr[m].append(n)

for row in arr :
    row.sort()

dfs(arr, V, visited)
print()
visited = [False for _ in range(N+1)]
bfs(arr, V, visited)
print()