题目描述

某大型公司的组织结构可以表示为一棵有根树。公司共有 $N$ 名员工，编号为 $1$ 到 $N$。员工 $1$ 是 CEO，也是这棵树的根。除 CEO 外，每名员工恰好有一名直接经理。

若存在一列员工

并且对每个 $i=1,2,\ldots,k-1$，$m_{i+1}$ 都是 $m_i$ 的直接经理，则称 $u$ 是 $v$ 的上级经理。注意：这里的“上级经理”包括直接经理。

公司管理层计划进行 $Q$ 次晋升。对于第 $i$ 次晋升，管理层选定一名员工 $c_i$，以及他当前的一名上级经理 $p_i$。晋升后，$p_i$ 将成为 $c_i$ 的直接经理。

为了避免路径上的其他员工不满，管理层决定同时调整从 $c_i$ 到 $p_i$ 路径上的所有员工。更形式化地说，设当前从 $c_i$ 沿直接经理关系走到 $p_i$ 的序列为：

那么晋升后，$m_1,m_2,\ldots,m_{k-1}$ 都会改为由 $p_i$ 直接管理。若 $k=2$，则所有人的直接经理保持不变。

管理层想知道这些晋升会如何影响公司内沟通的复杂程度。一次晋升之后，对每名员工统计他的上级经理数量；所有员工的这个数量之和，被定义为此时公司的沟通困难度。

请你在每次晋升之后，输出当前公司的沟通困难度。

输入格式

第一行输入两个整数 $N,Q$，分别表示员工数量和晋升次数。

接下来 $N-1$ 行，每行两个整数 $u_j,v_j$，表示在初始组织结构中，$u_j$ 是 $v_j$ 的直接经理。

接下来 $Q$ 行，每行两个整数 $p_i,c_i$，表示第 $i$ 次晋升后，$p_i$ 将成为 $c_i$ 的直接经理。

输出格式

输出 $Q$ 行，每行一个整数。

第 $i$ 行输出第 $i$ 次晋升后，公司的沟通困难度。

数据范围

• $1\le N,Q\le 10^5$；
• $1\le u_j,v_j,p_i,c_i\le N$；
• 保证初始组织结构是一棵以 $1$ 为根的树；
• 保证在第 $i$ 次晋升发生时，$p_i$ 是 $c_i$ 当前的一名上级经理。

子任务

只有通过某个子任务的全部测试点以及它依赖的所有子任务，才能获得该子任务的分数。

样例

输入

9 4
1 2
1 3
3 4
3 5
4 6
4 7
5 8
8 9
1 3
1 4
1 8
1 7

输出

19
16
11
10

样例解释

初始组织结构以及每次晋升后的组织结构如下图所示。