Cây là một cấu trúc dữ liệu quen thuộc trong tin học. Ví dụ ta có cây với nút như hình bên dưới.
Các nút được đánh số từ đến . Nút là gốc. Nút được gọi là nút cha của , nếu tồn tại một đường dẫn từ gốc tới đi qua . Ví dụ, nút là nút cha của nút , nút cũng là nút cha của . Một nút đồng thời là nút cha của chính mình. Như vậy, các nút , , và là nút cha của . Nút được gọi là nút cha chung của hai nút khác nhau và , nếu nó vừa là nút cha của , vừa là nút cha của . Ví dụ, các nút và đều là nút cha chung của các nút và . Nút được gọi là nút cha chung gần nhất của và , nếu nó là nút cha chung của hai nút này và trên đường dẫn từ tới không còn nút cha chung nào khác của và . Ở cây đang xét, là nút cha chung gần nhất của và .
Hãy lập trình tìm nút cha chung gần nhất của hai nút khác nhau của một cây có nút, các nút được đánh số từ tới .
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên - trong đó - số nút của cây, , là nút gốc;
dòng còn lại, mỗi dòng chứa hai số nguyên cho biết hai nút liên tiếp của cây;
Dòng cuối cùng chứa hai số nguyên khác nhau là hai nút cần tìm nút cha chung gần nhất.
