暂无测试数据。

给定一棵 $N$ 个节点的有根树，节点编号为 $1,2,3,…,n$，$1$ 号节点是根，每个节点上都有一个集合 $S$。

你需要进行 $Q$ 次操作，每次操作表示为两个正整数 $u\space x$，表示在 $u$ 及其子树内所有结点的集合都插入数 $x$。

操作完后，令 $f(y)$ 表示节点上的集合包含 $y$ 的节点个数，你需要对所有的正整数的 $f(y)$ 求和并输出。

输入格式

第一行两个正整数 $N,Q$。

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

接下来 $Q$ 行，每行两个正整数 $u,x$ 表示一个操作。

输出格式

输出一行一个整数表示所有 $f(y)$ 的和。

数据范围

对于所有数据，有 $1 \le N,Q \le 10^5;1 \le x \le 100$，保证给出的是一棵树。

对于 $20\%$ 的数据，有 $N,Q \le 10^3$。

对于另外 $20\%$ 的数据，有 $x=1$。

对于另外 $10\%$ 的数据，$Q \le 100$，每次操作的 $x$ 互不相同。

对于另外 $10\%$ 的数据，给出的树是一条链。

对于另外 $10\%$ 的数据，给出的树是一个菊花图。

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

8