問題文

頂点に $1, 2, \dots N$ の番号がついた $N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $A_{i}$ と頂点 $B_{i}$ を結んでいます。

木の各頂点は白か黒で塗られており、はじめ頂点 $i$ は $C_{i} = 0$ のとき白で、$C_{i} = 1$ のとき黒で塗られています。

$Q$ 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の $2$ 種類です。

• 1 v : 頂点 $v$ に塗られている色を反転する(白ならば黒に、黒ならば白に色を変える)。
• 2 x y : 以下の条件を全て満たす頂点 $v$ を良い頂点としたとき、良い頂点を全て含む連結部分グラフの頂点数の最小値を出力する。(ただし、良い頂点が存在しない場合は $0$ を出力すること。)
  • 頂点 $v$ は黒色で塗られている。
  • 頂点 $v$ と頂点 $x$ を結ぶ単純パスには頂点 $y$ が含まれる。

制約

• $1\leq N\leq 2\times 10^{5}$
• $1\leq A_{i} < B_{i}\leq N$
• 与えられるグラフは木である
• $C_{i}\in \{0, 1\}$
• $1\leq Q\leq 2\times 10^{5}$
• $1\leq v\leq N$
• $1\leq x\leq N$
• $1\leq y\leq N$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$\vdots$
$A_{N - 1}$ $B_{N - 1}$
$C_{1}$ $C_{2}$ $\dots$ $C_{N}$
$Q$
$\mathrm{query}_{1}$
$\mathrm{query}_{2}$
$\vdots$
$\mathrm{query}_{Q}$

各クエリ $\mathrm{query}_{i}$ は以下のいずれかの形式で与えられます。

$1$ $v$

$2$ $x$ $y$

出力

問題文の指示に従って、クエリへの答えを改行区切りで出力してください。

サンプル

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

7
7
1
0
3
4
1