74. 睡熊盲醒

睡熊盲醒

黑虎阿福是成龍歷險記的主角，又稱騷話王。他渾身肌肉武功高強，在做任何動作之前一定會喊出動作名子，可知其文學造詣非常良好。

這天阿福在睡覺時成龍和小蛇來偷他的符咒，不小心把阿福吵醒了，於是阿福立刻睜開眼喊出「睡熊盲醒！」，從這裡可以知道阿福神經傳導構造特別發達，在醒來的一瞬間就能喊出騷話。

阿福的腦神經構造可以當成是一顆$n$個點的無根樹，每個點代表一個神經元細胞。

在任何時刻下神經元細胞只有兩種狀態，一種是想揍扁成龍的狀態，一種是想說騷話的狀態，一開始時所有細胞都是處於想說騷話的狀態。

阿福只能對這些細胞做以下兩種操作：

• 0 u:
  詢問和編號$u$的神經細胞連通的細胞有多少個。我們說兩顆細胞$a,b$連通表示$a$到$b$的路徑(包括$a,b$)上所有細胞的狀態都相同。
• 1 u:
  改變編號$u$的神經細胞的狀態。如果$u$是處於想揍扁成龍的狀態就將它變成想說騷話的狀態；反之就將它變成想揍扁成龍的狀態。

現在給你阿福的腦神經構造以及阿福對這些細胞的操作，對於所有查詢操作請輸出他們的答案。

輸入

輸入第一行有一個正整數$n(1\le n\le 10^5)$表示神經細胞總數，接著有$n-1$行，每行有兩個數字$a,b$以空白隔開表示編號$a$的細胞和編號$b$的細胞存在一條edge相連。

再來有一個正整數$m(1\le m\le 2\times 10^5)$表示操作數量，之後的$m$行每行有兩個整數$t(0\le t\le 1),u(1 \le u\le n)$以空白隔開依序表示腦細胞做的操作(操作說明在題目敘述中)。

輸出

對於所有查詢操作請輸出一個正整數表示他們的答案。

範例輸入

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

範例輸出

7
3
3

子任務

• 子任務一($70\%$)：$n\leq 1000$ 且 $m\leq 20000$

• 子任務二($30\%$)：無限制

Judge Setting

run-time limit: 3000 ms
memory limit: 55360000 byte
測資數量: 9