깊이우선탐색과 너비우선탐색 (bfsdfs.cpp)

문제 그래프와 그래프를 이루고 있는 한 정점이 주어질 때, 그 정점으로부터 깊이 우선 탐색과 너비 우선 탐색을 하고 탐색한 순서대로 정점들을 출력하는 프로그램을 작성하시오. 만약 한 정점에서 갈 수 있는 정점이 여러 개일 경우 알파벳 순으로 빠른 정점을 우선한다.

입력 입력 파일의 첫 번째 줄에는 정의 개수 N과 간선의 개수 E가 주어진다. 정점은 A부터 차례대로 알파벳 대문자로 표현된다. 이어 E줄에 걸쳐 간선들의 정보가 주어지는데 간선의 정보는 간선의 두 양끝 정점으로 표현된다. 마지막 줄에는 탐색을 시작할 정점이 주어진다. N은 26 이하의 자연수, E는 100 이하의 자연수이며 그래프는 하나로 연결되어 있다.

출력 출력 파일의 첫째 줄에는 깊이 우선 탐색을 한 결과를, 둘째 줄에는 너비 우선 탐색을 한 결과를 출력한다.

예제 입력

7 9

A B

B E

A E

B C

E F

C F

C D

D G

G F

A

예제 출력

ABCDGFE

ABECFDG