그래프의 정보(vertex 수, edge 정보)와 시작 정점의 번호가 주어질 때, 깊이우선탐색(DFS)으로 방문할 때 정점의 방문 순서를 출력하는 프로그램을 작성하시오.

입출력 예에서 주어진 그래프는 다음과 같은 형식이다.

입력 형식

입력의 첫째 줄에는 정점의 수와 시작정점의 번호가 입력되고, 다음 부터는 정점의 쌍으로 간선(edge)을 표현한다.

정점 수는 최대 10 개이고 , 1 부터 순차적으로 번호가 부여되어 있다.

입력의 끝은 EOF 이다.

출력 형식

시작정점에서 방문되는 정점번호를 출력한다. 답이 여러개 존재하는 경우 사전식 순으로 먼저 나오는 것을 출력한다.

입출력 예

입력

8 1
1 2
1 3
2 4 
2 5
3 6 
3 7
4 8 
5 8
6 8
7 8

출력

1 2 4 8 5 6 3 7

참고 사항

• 깊이 우선탐색 (Depth First Search)
  스택구조를 이용한다.
  쉽게 생각해서 찐더기 방식이다. 걸리면 걸리는 쪽으로 엉겨 붙는다. 더 이상 엉겨붙을때가 없으면 바로 전에 엉기다 만데로 돌아온다.
• 너비 우선탐색(Breadth First Search)
  큐를 이용한다.
  현재 정점에 연결된 정점을 모두 방문하면서 , 큐에 삽입후 큐에서 정점을 하나를 가져온후 같은 방식으로 방문한다.

깊이 우선 탐색(DFS)

-1 에서 1 은 자신이고 2 번 정점으로 
       -2 번 정점에서는 1 번은 이미 방문되었고 2 는 자신이고 3, 4 번은 연결이 되지 않았고 5 번으로 
          -5 번 정점에서 1 은 연결x , 2 번은 이미 방문, 3 번 정점으로 
             -3 번 정점에서는 1 은 이미 방문 , 2 번은 연결 x , 4 번은 연결 x , 5 번은 이미 
              방문되었으므로 갈 때가 없으니 바로 전 단계로 return 
          -5 번 정점은 3 번 다음 정점 4 번 정점으로 
             -4 번 정점은 1 은 이미 방문 2,3 은 연결x , 5 번은 이미 방문 return 
          -5 번 정점은 5 에서 return
       -2 번 정점에서 5 다음이 없으므로 return 
-1 에서 2 다음은 3,4,5 는 이미 방문되었으므로 return