問題文

$N$ 頂点の木が与えられる。$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいる。

はじめ、頂点 $v$ には数 $v$ が書かれている。$f(u, v)$ を $u-v$ パス上の頂点に書かれた数を順に並べた数列とする。

以下のクエリに $Q$ 回答えよ。

• u v: 頂点 $u$ と頂点 $v$ に書かれた数を入れ替える。その後、$\mathrm{argmax}_w f(u, w)$ を出力する（数列の大小比較は辞書順）

入力

$N$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$
$Q$
$u_1\ v_1$
$\vdots$
$u_Q\ v_Q$

(2021/12/16 01:47 修正)ただし、クエリは暗号化されている。$i$ 番目のクエリについて、直前のクエリの答えを $x$ としたとき（$i = 1$ のときは $x = 0$ とする）、$(u, v) = (((u_i + x) \bmod N) + 1, ((v_i + x) \bmod N) + 1)$ としてクエリに答えよ。

ただし、クエリは暗号化されている。$i$ 番目のクエリについて、直前のクエリの答えを $x$ としたとき（$i = 1$ のときは $x = 0$ とする）、$(u, v) = (((u_i + N - 1 + x) \bmod N) + 1, ((v_i + N - 1 + x) \bmod N) + 1)$ としてクエリに答えよ。

• $2 \le N \le 2 \times 10^5$
• $1 \le a_i, b_i \le N$
• 与えられるグラフは木をなす
• $1 \le Q \le 2 \times 10^5$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$

出力

$Q$ 行出力せよ。$i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。最後に改行せよ。

サンプル

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

1
3
3
3

10
9 8
10 3
2 3
10 9
1 10
6 4
4 1
1 5
6 7
15
8 10
2 8
9 8
8 2
9 1
2 8
1 4
4 1
6 2
6 9
7 8
4 2
4 3
10 2
1 9

2
7
5
8
5
5
5
8
7
8
2
7
5
7
5