#1419. PEACE - Chó, Mèo và Chuột

Cho một cây gồm đỉnh đánh số từ tới . Ba con vật nuôi: Chó, mèo và chuột đứng ở ba đỉnh khác nhau. Chó biết rằng mèo đôi lúc hay bắt nạt chuột và khi đó mèo sẽ di chuyển theo các cạnh trên cây tới nơi chuột đứng. Chó muốn ngăn cản mèo bắt chuột bằng cách di chuyển tới một đỉnh nào đó trên đường đi từ vị trí của mèo tới vị trí của chuột, tuy nhiên do quá béo và lười nên chó muốn chọn đỉnh gần nhất để đi tới.

Yêu cầu: Trả lời truy vấn, mỗi truy vấn cho bởi ba số nguyên hoàn toàn phân biệt lần lượt là vị trí của chó, mèo và chuột. Hãy cho biết vị trí của chó cần đi tới

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ;
• dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ứng với một cạnh trên cây;
• dòng tiếp theo, mỗi dòng chứa ba số nguyên hoàn toàn phân biệt ứng với một bộ vị trí của chó, mèo và chuột.

Dữ liệu ra:

• Ghi ra dòng, mỗi dòng ghi số hiệu đỉnh là câu trả lời cho một truy vấn.

Ví dụ:

Dữ liệu vào:

6 4
1 2
1 3
3 4
3 5
5 6
1 2 3
5 2 4
6 2 5
6 3 4

Dữ liệu ra:

1
3
5
3