트리는 컴퓨터 공학에서 유명한 자료구조이다.

그림에서 각 노드는 1,2,3...,16 의 정수 번호가 부여되어 있다. 노드 8 은 이 트리의 루트이다. 노드 x 는 노드 y 와 루트 사이의 패스에 존재하면 조상이라고 한다. 노드 4 는 노드 16 의 조상이다. 노드 10 은 노드 16 의 조상이다.

8,4,10,16 은 노드 16 의 조상이다. 임의의 노드는 자신의 조상이라는 것을 명심하라.

노드 8,4,6,7 은 노드 7 의 조상이다. 노드 x 는 다른 두 노드이 y,z 의 공통조상 이라고 한다. x 가 y 의 조상이고 , x 가 z 의 조상이라면...

노드 8 , 4 는 노드 16 과 7 의 조상이다. 노드 x 는 y,z 의 조상이면서 , 가장 가까운 조상이면 nca(nearest common ancestor) 라 한다. 16 과 7 의 nca 는 노드 4 이다. 16 과 7 의 nca 는 노드 8 이 아닌 노드 4 이다. 2 , 3 의 nca 는 10 이고, 6 , 13 의 nca 는 8 , 4 ,12 의 nca 는 노드 4 이다.

입력

노드수는 2 이상 10,000 이하이고 , 노드는 1 에서 n 까지 번호가 부여된다.

tree 구조에서는 n 개의 node 를 가지는 경우 n-1 개 branch 를 가지는 구조라는 것을 명심하라.parents 와 child 정보가 주어진다. 마지막 번호는 2 개의 노드 번호가 주어지고 , 이 두 노드의 nca 를 구하는 것이다.

출력

입출력 예

입력

16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7

출력

4

입력

5
2 3
3 4
3 1
1 5
3 5

출력

3

출처:Taejon 2002