Bitset Master

It is well known in China that $O(n^2)$ algorithms can pass a problem with $n = 10^6$ easily.

You are given a tree with $n$ vertices and $n - 1$ edges $(u_1, v_1), (u_2, v_2), \ldots, (u_{n-1}, v_{n-1})$. Each vertex $u$ has a set $S_u$. Initially $S_u = \{u\}$.

There are two types of operations.

• "1 u": output the number of sets $S_v$ ($1 \le v \le n$) that contain $u$.
• "2 p": take the sets $S_{u_p}$ and $S_{v_p}$, where $(u_p, v_p)$ is the $p$-th edge, and assign $S_{u_p} \cup S_{v_p}$ to both of them.

You need to perform $m$ operations. Output the answer for each operation of the first kind.

The time limit is 6000 ms and the memory limit is 512 MB.

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le 6 \times 10^5$).

Each of the following $n - 1$ lines contains two integers $u_i$ and $v_i$ describing an edge ($1 \le u_i, v_i \le n$).

Each of the following $m$ lines contains two integers $t$ and $w$ describing an operation ($1 \le t \le 2$, $1 \le w \le n + 1 - t$).

For each operation of the first kind, output an integer on a separate line.