給定一個包含 $N$ 個頂點的樹（無環無向連通圖）。頂點編號由 $1$ 至 $N$，邊編號由 $1$ 至 $(N-1)$。

請撰寫一個程式來執行以下查詢：

• $u$ $v$：對於所有頂點 $x$（$1 \le x \le N$），輸出 $\operatorname{dist}(x, u) + \operatorname{dist}(x, v)$ 的最大值。（$1 \le u, v \le N$）

其中 $\operatorname{dist}(x, y)$ 定義為從頂點 $x$ 到頂點 $y$ 的最短路徑上的邊數。對於樹中的所有頂點 $x$，$\operatorname{dist}(x, x) = 0$。

輸入格式

第一行給定樹的頂點數 $N$。（$2 \le N \le 300000$）

接下來的 $(N-1)$ 行給定樹的資訊。其中第 $i$ 行包含兩個以空格分隔的整數，代表第 $i$ 條邊所連接的兩個頂點編號。

下一行給定查詢次數 $Q$。（$2 \le Q \le 300000$）

接下來的 $Q$ 行，每行給定一個查詢的資訊。

輸出格式

依序輸出 $Q$ 個查詢的答案，每個答案佔一行。

範例

輸入格式 1

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

輸出格式 1

6
5
5