相互选择

时间限制：$4$ 秒。内存限制：$512$ MB。

题目描述

给定一棵有 $n$ 个顶点的树，顶点编号为 $1,2,\ldots,n$。顶点 $i$ 的分数为 $p_i$，其中 $p_1,p_2,\ldots,p_n$ 是 $1,2,\ldots,n$ 的一个排列。每个顶点都选择与它直接相连的顶点中分数最小的一个。

依次进行 $q$ 次交换。每次给出两个顶点 $u,v$，交换它们的分数 $p_u,p_v$。

每次交换后，所有顶点按当前分数重新选择。求有多少对顶点 $\{x,y\}$，满足 $x$ 选择 $y$，并且 $y$ 也选择 $x$。每对顶点只计数一次。

每次交换立即生效，后续交换使用当前分数。

输入格式

输入文件：choice.in。

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树的一条边。

接下来 $q$ 行，每行包含两个整数 $u,v$，表示交换这两个顶点的分数。

输出格式

输出文件：choice.out。

对每次交换，输出一行一个整数，表示交换后互相选择的顶点对数。

样例

输入：

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

输出：

1
1
1
2

样例解释

前三次交换后，互相选择的顶点对依次为 $\{3,4\}$、$\{2,3\}$、$\{1,2\}$。第四次交换后，$\{1,2\}$ 与 $\{3,4\}$ 都互相选择，答案为 $2$。

附加样例 $\texttt{choice2.in/.ans}$、$\texttt{choice3.in/.ans}$、$\texttt{choice4.in/.ans}$、$\texttt{choice5.in/.ans}$ 分别满足测试点 $3\sim5$、$6$、$7\sim8$、$15\sim20$ 的限制。

数据范围

对于所有测试点，$2\le n\le10^6$，$1\le q\le10^6$，$1\le u,v\le n$。保证给出的图是一棵树，$p_1,p_2,\ldots,p_n$ 是 $1,2,\ldots,n$ 的一个排列。

特殊性质 $A$：每个顶点的度数均不超过 2。

特殊性质 $B$：每次交换的两个顶点在原树中的度数均不超过 10。