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

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

• 1 i: 頂点 $i$ の色を反転する (白 → 黒, 黒 → 白)
• 2 u: 頂点 $u$ と連結している頂点 $v$ の個数を数える。2 つの頂点が連結しているとは、それらを結ぶ経路上のすべての頂点の色が同じであることを意味する。

入力

最初の行に $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 つずつ出力する。

入出力例

入力 1

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

出力 1

5
1

入力 2

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

出力 2

7
3
3