题目描述

小可可练习完树上邻域数颜色之后，又想出来一个关于树的题拿来问你。

有一颗 n 个点的树和 n 个集合 Si，初始时 Si = {i}。

有 q 次操作，每次操作分为两种：

• 1 u (1 ≤ u ≤ n)：询问有多少 v 满足 u ∈ Sv。

• 2 i (1 ≤ i < n)：设输入的第 i 条边为 (ui, vi)，则将 Sui, Svi 改为 Sui ∪ Svi。 小可可想知道所有 1 操作的答案是什么。

输入格式

第一行两个正整数 n, q，表示树的大小和操作个数。

接下来 n − 1 行每行两个整数 ui, vi，表示树的第 i 条边。

接下来 q 行每行两个整数，表示一次操作。

输出格式

对于每次 1 操作，输出一行一个整数表示对应答案。

样例输入1

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

样例输出1

5
2
3
4
5

样例2/3

见下发文件。

数据规模及约定

对于 20% 的数据，n ≤ 10^3, 1 ≤ q ≤ 10^4；

对于另外 20% 的数据，ui = 1, vi = i + 1；

对于另外 20% 的数据，ui = i, vi = i + 1；

对于 100% 的数据，1 ≤ n ≤ 2 × 10^5, 1 ≤ q ≤ 6 × 10^5。