Informatica Online Judge

  LCA(small) [1691 / 069B]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 67   Total Tried : 70


The Champion of this Problem (C++) : kdh9949 - ms / 561byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

$N$개 의 정점으로 이루어진 트리가 주어진다.

트리의 각 정점은 $1$번부터 $N$번까지 번호가 매겨져 있으며, 루트는 $1$번이다.

두 노드의 쌍 $M$개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

Input

첫째줄에 노드의 총 쌍이 주어진다.

둘째줄부터는 노드의 쌍이 $M$개만큼 주어진다.

마지막 줄에는 가장 가까운 공통 조상을 알기 원하는 노드 쌍이 주어진다.

[입력값의 정의역]

$2 ≤ N < 2500$ $2 ≤ M ≤ 2500$

Output

입력받은 두 노드의 가장 가까운 공통 조상을 출력한다.

IO Example

입력
12
1 2
1 3
3 10
3 11
3 12
3 13
2 4
4 5
5 6
5 7
5 8
5 9
6 9

출력
5

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