$N$ 個の頂点からなる木 (無向サイクルのない連結グラフ) がある。頂点には $1$ から $N$ までの番号が、辺には $1$ から $N-1$ までの番号が付けられている。最初、すべての頂点の色は白である。

以下の 2 種類のクエリを実行するプログラムを作成せよ。

• 1 i: 頂点 i の色を反転する (白→黒、黒→白)。
• 2 v: 頂点 1 から頂点 v へのパス上にある最初の黒い頂点の番号を出力する。そのような頂点が存在しない場合は -1 を出力する。

入力

最初の行に $N$ ($2 \le N \le 100{,}000$) が与えられる。

次の $N-1$ 行には、i 番目の辺が接続する 2 つの頂点番号 $u$ と $v$ が与えられる。

次の行にはクエリの個数 $M$ ($1 \le M \le 100{,}000$) が与えられる。

次の $M$ 行には、クエリが 1 行に 1 つずつ与えられる。

出力

2 番目のクエリの結果を順に 1 行ずつ出力せよ。

入出力例

入力 1

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

出力 1

-1
8
-1
2
-1