Background

土拨鼠文景刚刚学习了集合的概念, 了解到在集合中, 相同的元素最多只有一个.

集合（数学概念）_百度百科 (baidu.com)

Description

给你一棵$n$个节点的树, 节点编号为$1, 2, 3... n$, 其中$1$号节点是根节点, 每个节点都有一个集合$s$.

你需要进行$q$次操作, 每次操作给出两个正整数$u, x$, 表示将$x$插入$u$及其子树内所有节点所在的集合.

操作完后, 令$f(y)$表示包含$y$元素的集合的个数, 计算对于所有的正整数$y$, 求所有$f(y)$的和.

Format

Input

第一行两个正整数$n, q$

接下来$n-1$行, 每一行两个正整数, 表示树的一条边

接下来$q$行, 每行两个正整数$u, x$, 表示依次操作

Output

输出一个整数表示所有$f(y)$之和.

Samples

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

8

样例解释

第一次操作, $1, 2, 3, 4, 5$号节点的集合都插入了$1$.

第二次操作, $3, 4, 5$号节点的集合都插入了$2$

第三次操作, $4$号节点的集合插入了2, 但是$f(2)$的值并没有发生改变

包含$1$元素的集合一共有$5$个, $f(1) = 5$, 包含$2$元素的集合一共有$3$个, $f(2) = 3$, 固答案为$8$.

Limitation

$1 <= n, q <= 10^5, 1<=x <= 100, 1<=u <= n$