バックアップ1260:DFSとBFS

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)
    graph[B].append(A)

#DFS
visited = []
stack = [V]

while stack:
    tmp = stack.pop()
    if tmp not in visited:
        visited.append(tmp)
        plus = list(set(graph[tmp]) - set(visited))
        plus.sort(reverse=True)
        stack += plus
        
for i in range(len(visited)):
    print("{} ".format(visited[i]), end="")
print()

#BFS
visited = []
queue = deque([V])

while queue:
    tmp = queue.popleft()
    if tmp not in visited:
        visited.append(tmp)
        plus = list(set(graph[tmp]) - set(visited))
        plus.sort()
        queue += plus
        
for i in range(len(visited)):
    print("{} ".format(visited[i]), end="")
print()