# Câu 3 : (4.0 điểm) Nút cha chung gần nhất

Cây là một cấu trúc dữ liệu có nhiều ứng dụng trong tin học. Ví dụ ta cso cây với $16$ nút, các nút được đánh số từ 1 tới $16$, nút $8$ là gốc, như hình sau :

Nút $x$ được gọi là nút cha của $y$ nếu tồn tại một đường dẫn từ gốc tới $y$ đi qua $x$. Ở cây đang xét, nút $4$ là nút cha của nút $16$, nút $10$ cũng là nút cha của $16$.


Một nút đồng thời là nút cha của chính mình. Ở cây đang xét, các nút $8, 4, 10$ và $16$ là nút cha của $16$

Nút $x$ được gọi là nút cha chung của 2 nút khác nhau $y$ và $z$ nếu nó vừa là nút cha của $y$, vừa là của $z$. Ở cây đang xét, các nút $8$ và $4$ đều là nút cha chung của các nút $7$ và $16$.

Nút $x$ được gọi là nút cha chung gần nhất của $y$ và $z$ nếu nó là nút cha chugn của 2 nút này và trên đường dẫn từ $x$ tới $y$ không còn nút cha chung nào khác của $y$ và $z$. Ở cây đang xét, $4$ là nút cha chung gần nhất của $7$ và $16$.

Cho một cây gồm $N$ nút, các nút được đánh số từ $1$ đến $N$.

**Yêu cầu**

Xác định nút cha chung gần nhất của 2 nút khác nhau trên cây

**Input**

*Dòng 1* : Chứa 2 số nguyên dương $N$ và $K$. Trong đó $N$ là số lượng nút cây, $K$ là chỉ số nút gốc. $(2<=N<=10000)$

*$N-1$ dòng tiếp theo :* mỗi dòng chứa 2 số nguyên dương $x$ và $y$ , là chỉ số 2 nút liên tiếp cây với $x$ là nút cha của nút $y$.

*Dòng cuối cùng :* chứa 2 số nguyên khác nhau là chỉ số 2 nút cần tìm nút cha chung gần nhất.

Các số trên cùng 1 dòng được ghi cách nhau ít nhất một dấu cách.

**Output**

*Dòng 1* : Ghi một số nguyên dương là chỉ số nút cha chung gần nhất tìm được.

**Example**

> **Input**
>
> 16 8
> 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

> **Output**
>
> 4