题目描述

绵阳动物园即将召开全园动物代表大会，现任领导小老虎提出了关于修改动物园基本法的提案。

动物园有 $n$ 只动物，动物们的家构成了一棵树，初始第 $i$ 只动物在节点 $i$，其中小老虎的家是 $1$，也是大会召开的地方。

现在所有动物要赶往 $1$ 号节点，动物们非常喜欢一起行走，当一个动物走到 $u$ 号节点，它会等待所有会经过 $u$ 号节点的所有动物，直到它们都到达了 $u$ 号节点，然后一起向 $1$ 号节点走去。

每个节点 $u$ 都会有一个冰淇淋店，节点 $u$ 的冰淇淋售价为 $a_u$，质量为 $b_u$。当两只动物第一次走到同一个节点 $u$ 时，它们会互相赠送给对方一个该节点售卖的冰淇淋。

对于每只动物，任意两个它收到的冰淇淋 $(i, j)$ 满足 $a_i < a_j\land b_i > b_j$，那么会给它产生 $1$ 的愉悦度。

现在想知道所有动物的愉悦度之和。

除此之外会有 $q$ 个独立事件：

• 1 u：第 $u$ 只动物消失了。
• 2 u v：第 $u$ 只和第 $v$ 只动物消失了（$u\ne v$）

你需要对每个事件回答所有动物的愉悦度之和。

输入格式

第一行两个整数 $n, q$，代表树的大小和事件个数。

接下来 $n$ 行每行两个整数 $a_i, b_i$。

接下来 $n - 1$ 行每行两个整数 $u_i, v_i$ 表示树边。

最后 $q$ 行描述每个事件。

输出格式

输出 $q + 1$ 行，第一行输出没有动物消失的愉悦度之和，剩下 $q$ 行回答每个询问。

样例输入 #1

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

样例输出 #1

6

样例输入 #2

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

样例输出 #2

12
4
4
6
4
6

样例输入 #3

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

样例输出 #3

12
2
2
0
2
2

样例文件 #4-#6

见下发文件。

数据范围

对于所有的数据满足 $1\le n, q\le 1.5\times 10^5$，$1\le a_i, b_i\le n$，保证所有 $a_i$ 互不相同，所有 $b_i$ 互不相同。

子任务编号	特殊性质	空间限制	分值
1	$q = 0$	$512MB$	$15$
2		$256MB$	$5$
3	所有事件都是类型 $1$	$512MB$	$15$
4		$256MB$	$5$
5	无	$512MB$	$30$
6		$256MB$

提示

题目顺序是瞎排的。