THỰC HÀNH

Xét một cây với n nút (đồ thị liên thông n đỉnh, không có chu trình).

• Nút X được gọi là nút cha của nút Y (hay Y là con của X) nếu trên đường đi từ gốc tới Y có đi qua X (X còn gọi là tiền bối của Y còn Y gọi là hậu duệ của X).
• Nút X được gọi là nút cha chung của Y và Z nếu X đồng thời la cha của Y và của Z.
• Nút X được gọi là nút cha chung gần nhất của Y và Z nếu X là cha chung của Y và Z, ngoài ra không có nút nào là cha chung của Y và Z mà lại là con của X.Có thể phát biểu theo những cách khác như sau: X là nút cha chung gần nhất của Y và Z nếu X là nút xa gốc nhất là cha chung của Y và Z, hoặc: X là nút cha chung gần nhất của X và Y nếu X là nút cha chung của Y và Z mà trên đường đi đơn từ X đến Y và từ X đến Z không đi qua bất cứ một nút chung nào khác X.

Bài toán: Cho cây T và hai nút X, Y. hãy tìm nút cha chung gần nhất của hai nút X và Y.

Dữ liệu vào:

• Dòng đầu chưa hai số nguyên dương N, K là số nút của cây và số hiệu nút gốc.
• N - 1 dòng tiếp theo mỗi dòng chưa hai số nguyên u, v cho biết u và v là hai đỉnh liên tiếp trên cây (u là cha trực tiếp của v hoặc ngược lại)
• Dòng cuối cùng chứa hai số nguyên X, Y là số hiệu hai nút cần tìm cha chung gần nhất.

Dữ liệu ra:

Một số nguyên duy nhất là số hiệu nút cha chung gần nhất củ X và Y.

Ví dụ:

Dữ liệu vào:
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
Dữ liệu ra:
4

Giới hạn: 2 ≤ N ≤ 10000; 1 ≤ K, X, Y, u, v ≤ 10000; u ≠ v.