DFS

그래프 탐색깊이 우선 탐색

$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 간선으로 이루어진 무방향 그래프가 있다.

정점 $S$에서 DFS를 시작하여 정점을 방문하는 순서대로 출력하라.

방문할 수 있는 정점이 여러 개라면 번호가 작은 정점을 먼저 방문한다.

입력

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 시작 정점 $S$가 주어진다. $(1 \leq N \leq 100\,000,\ 0 \leq M \leq 200\,000,\ 1 \leq S \leq N)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선으로 연결된 두 정점 $u$, $v$가 주어진다. $(1 \leq u,v \leq N,\ u \neq v)$

같은 간선은 두 번 이상 주어지지 않는다.

정점 $S$에서 DFS를 수행했을 때 방문하는 정점을 순서대로 출력한다.

정점 번호는 공백으로 구분한다.

1 2 4 5 3 6