깊이우선탐색(DFS)는 그래프의 임의의 한 정점에서 출발하여, 연결된 정점들 중 하나에 대해서 깊이 순으로 먼저 탐색해 나가는 탐색법이다. 예를 들어 다음과 같은 그래프를 보자.

이를 정점 1을 시작으로 깊이우선 탐색을 했을 경우 여러가지가 가능하지만 가능한 경우의 한 가지는

1 2 3 5 6 4 이다.

따라서 하나의 결과를 위해 다음과 같은 제약조건을 적용한다.

1. 정점 1부터 방문한다.

2. 한 정점에서 갈 수 있는 곳이 여러개 있을 경우 먼저 입력된 정점부터 방문한다.

3. 어떤 정점과 연결되지 않은 경우는 번호가 빠른 순으로 방문한다.

주어진 그래프는 양방향 무가중치 그래프이다.

DFS결과를 출력하라.