from collections import deque
import sys
N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited_DFS = [0] * (N+1)
visited_BFS = [0] * (N+1)
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
graph[a] += [b]
graph[b] += [a]
def DFS(V):
visited_DFS[V] = 1
print(V, end=' ')
for i in sorted(graph[V]):
if visited_DFS[i] == 0:
DFS(i)
def BFS(V):
queue = deque()
queue.append(V)
visited_BFS[V] = 1
while queue:
a = queue.popleft()
print(a, end=' ')
for i in sorted(graph[a]):
if visited_BFS[i] == 0:
visited_BFS[i] = 1
queue.append(i)
DFS(V)
print()
BFS(V)
DFS/BFS 함수를 이용하여 각각의 순서를 출력한다.
처음 연결된 노드들을 입력할 때 각 노드의 연결된 노드들은 순서대로 추가되지 않는 것을 주의해야한다.
이를 위해 각 함수의 그래프 내 원소의 연결된 원소를 하나씩 가져오는 for문에서 sorted()함수를 이용하여 원소 내의 연결된 원소들을 오름차순으로 만들어주어야 한다.