// problem #64

DFS와 BFS

정점 번호가 작은 것부터 방문하는 규칙으로, 시작 정점 V에서의 DFS 방문 순서와 BFS 방문 순서를 각각 출력하시오.

입력

첫 줄 정점 수 N, 간선 수 M, 시작 정점 V. 이후 M개 줄에 간선 a b.

출력

첫 줄 DFS 순서, 둘째 줄 BFS 순서.

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 10,000

예제

4 5 1
1 2
1 3
1 4
2 4
3 4

1 2 4 3
1 2 3 4

5 5 3
5 4
5 2
1 2
3 4
3 1

3 1 2 5 4
3 1 4 2 5