비트셋 마스터

중국에서는 $n = 10^6$인 문제에서도 $O(n^2)$ 알고리즘이 쉽게 통과한다는 것이 잘 알려져 있다.

정점이 $n$개이고 간선이 $n-1$개인 트리가 주어진다. 간선은 $(u_1, v_1), (u_2, v_2), \ldots, (u_{n-1}, v_{n-1})$이다. 각 정점 $u$마다 집합 $S_u$가 있으며, 처음에는 $S_u = \{u\}$이다.

연산은 두 종류이다.

• "1 u": $u$를 포함하는 집합 $S_v$ ($1 \le v \le n$)의 개수를 출력한다.
• "2 p": $p$번째 간선 $(u_p, v_p)$의 두 끝점에 해당하는 집합 $S_{u_p}$와 $S_{v_p}$를 합집합 $S_{u_p} \cup S_{v_p}$로 둘 다 바꾼다.

$m$개의 연산을 수행한다. 첫 번째 종류의 연산마다 답을 구한다.

시간 제한은 6000 ms, 메모리 제한은 512 MB이다.

첫 줄에 정수 $n$과 $m$이 주어진다 ($2 \le n \le 2 \times 10^5$, $1 \le m \le 6 \times 10^5$).

이어서 $n-1$개의 줄에 간선을 나타내는 정수 $u_i$와 $v_i$가 주어진다 ($1 \le u_i, v_i \le n$).

이어서 $m$개의 줄에 연산을 나타내는 정수 $t$와 $w$가 주어진다 ($1 \le t \le 2$, $1 \le w \le n + 1 - t$).

첫 번째 종류의 연산마다 답을 한 줄에 정수 하나로 출력한다.