<reponame>ki-yungkim/Algorithm_Step_1_Stack_Queue<gh_stars>0

graph = {}
n = input().split(' ')
node, edge, start = map(int, n)
for i in range(edge):
    edge_number = input().split(' ')
    n1, n2 = map(int, edge_number)
    
    if n1 not in graph:
        graph[n1] = [n2]
    elif n2 not in graph[n1]:
        graph[n1].append(n2)

    if n2 not in graph:
        graph[n2] = [n1]
    elif n1 not in graph[n2]:
        graph[n2].append(n1)


def DFS(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in graph:
                tmp = list(set(graph[n]) - set(visited))
                tmp.sort(reverse=True)
                stack += tmp
    return " ".join(map(str, visited))

def BFS(graph, start):
    visited = []
    queue = [start]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            if n in graph:
                tmp = list(set(graph[n]) - set(visited))
                tmp.sort()
                queue += tmp
    return " ".join(map(str, visited))
  
print(DFS(graph, start))
print(BFS(graph, start))

graph = {}
n = input().split(' ')
node, edge, start = map(int, n)
for i in range(edge):
    edge_number = input().split(' ')
    n1, n2 = map(int, edge_number)
    
    if n1 not in graph:
        graph[n1] = [n2]
    elif n2 not in graph[n1]:
        graph[n1].append(n2)

    if n2 not in graph:
        graph[n2] = [n1]
    elif n1 not in graph[n2]:
        graph[n2].append(n1)


def DFS(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in graph:
                tmp = list(set(graph[n]) - set(visited))
                tmp.sort(reverse=True)
                stack += tmp
    return " ".join(map(str, visited))

def BFS(graph, start):
    visited = []
    queue = [start]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            if n in graph:
                tmp = list(set(graph[n]) - set(visited))
                tmp.sort()
                queue += tmp
    return " ".join(map(str, visited))
  
print(DFS(graph, start))
print(BFS(graph, start))