Informatica Online Judge

  중간경로 점 찾기 [2139 / 085B]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 21   Total Tried : 21


The Champion of this Problem (C++) : gs16106 - 0ms / 493byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs15018]

Background

n개의 점, n-1개의 간선으로 이루어지고 임의의 두 점 사이 경로가 존재하는 그래프가 있다.

경곽이는 두 점을 선택하여 간선을 따라 연결하는 경로를 그리고 싶지만 눈이 나빠서 어떤 경로를 따라가야 하는지 한눈에 알 수 없다.

눈이 나쁜 경곽이를 위해 중간에 지나가야 하는 점들을 순서대로 알려주자.

Input

첫 번째 줄에 점의 갯수(10000 이하)가 입력된다.

두 번째 줄부터 n-1개의 줄에 간선의 연결 상태가 입력된다. 마지막 줄에 시작점, 끝점이 순서대로 입력된다.

Output

시작점, 끝점을 포함하여 중간 경로의 점들을 한 칸씩 띄어 출력한다.

IO Example

입력
7
1 6
2 6
4 6
6 7
7 3
3 5
1 3

출력
1 6 7 3



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]