問題文

$N$ 頂点の木が与えられます．$i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます．
今，全ての頂点は白色で塗られています．$Q$ 個のクエリを処理してください．

各クエリは以下のいずれかの形です．

• 1 v: 頂点 $v$ の色がクエリの直前の時点で白色ならば黒色に，黒色ならば白色に変更する．
• 2 v: 頂点 $v$ と黒色の頂点の距離としてありうる最小の値を出力する．このクエリの時点で黒色の頂点が存在することは保証される．

入力

$N$
$U_1\ \ V_1$
$U_2\ \ V_2$
$\vdots$
$U_{N - 1}\ \ V_{N - 1}$
$Q$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\vdots$
$\mathrm{Query}_Q$

• $2 \leq N \leq 10^5$
• $1 \leq U_i < V_i \leq N$
• $1 \leq Q \leq 10^5$
• $1 \leq v \leq N$
• 入力はすべて整数
• 与えられるグラフは木である
• 2 から始まるクエリの時点で黒色の頂点が存在する

出力

2 から始まるクエリに応じて，出力するべき内容を出力し，改行してください．

サンプル

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

3
2
0
2

2
1 2
5
1 2
2 1
2 2
1 1
2 1

1
0
0