最近的共同主管

題目敘述

某公司有 n 位員工，編號 1 到 n，其中 1 號是總經理，其餘每人恰有一位直屬主管，整個公司用 n−1 條「主管－部屬」關係連成一棵樹。對兩位員工 a、b，把各自往上追溯到總經理所經過的所有人（包含自己）列出來，兩份名單共有的人中，離總經理最遠的那一位，就是他們最近的共同主管。對每組詢問輸出這個人的編號。

輸入格式

• 第一行有兩個整數 n、q。
• 接下來 n−1 行，每行兩個整數 u、v，表示節點 u 與 v 之間有一條邊。
• 再接下來 q 行，每行兩個整數 a、b，代表一組詢問。

輸出格式

輸出 q 行，依序對應每組詢問，每行一個整數，為 a 與 b 的最近共同祖先（以 1 為根）的編號。

限制

• 2 ≤ n ≤ 200
• 1 ≤ q ≤ 200

範例

範例 1

輸入

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

輸出

3
1

範例 2

輸入

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

輸出

1
3
1

範例 3

輸入

2 1
1 2
1 2

輸出

1

說明

第一組詢問中，4 與 5 都是 3 的子節點，所以答案為 3；第二組詢問中，2 與 4 要往上走到根 1 才會會合，答案為 1。