题目描述

在你面前有一个树，树上的各个节点值均不重复。初始时，树上的所有节点都是黑色。 现在我们要进行m次操作，每次操作输入3个数 $[p, x, y]$表示：

p 等于 0 时，我们将所有节点数值在 [x, y] 的点全部染成黑色
p 等于 1 时，我们将所有节点数值在 [x, y] 的点全部染成红色

现在请你想一个办法，在我们进行完全部的操作后输出红色点的数量

输入格式

第一行包含两个整数$n(1 \leq n \leq 10^5)$ 和$m(0 \leq m \leq 10^5)$ ,表示给定顶点数和操作数

随后给你$n-1$行输入，每行包含三个整数$u,v(0 \leq u,v \leq 10^9)$表示点$u$和点$v$间相连接

随后给你$m$行输入，每行包含三个整数$p,x,y(0 \leq x \leq y \leq 10^9)$,表示我们的操作

输出格式

输出一个整数，表示在进行$m$次操作后红色节点的数量

样例

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

4

提示

对于样例1

第一次操作将点2染成黑色

第二次操作将点1，2，3，4，5染成红色

第三次操作将点4，5染成黑色

第四次操作将点5染成红色

四次操作后我们有点1，2，3，5四个点为红色