Batyr 最近開始研究樹。但他並非樹木學家，因此他研究的是具有 $n$ 個頂點和 $n - 1$ 條邊的連通圖的性質。

假設 $T$ 是一個具有 $n$ 個已編號頂點的無向樹。Batyr 定義了一個函數 $f(S)$：包含 $S$ 中所有頂點的 $T$ 的連通子圖的最小大小（節點數），其中 $S$ 是 $T$ 的任意頂點子集。換句話說，想像刪除 $T$ 中儘可能多的頂點，使得 $S$ 中的所有頂點保持連通。所得樹的大小即為 $f(S)$。

作為一名高級研究員，Batyr 對這些瑣事並不滿足。他已經選定了一棵樹 $T$ 並將其畫在白板上。然後，他在每個頂點上都貼了一個帶有 $1$ 到 $n$ 之間唯一數字的小磁鐵。頂點的索引與其上磁鐵的數字可能不同：帶有數字 $p_i$ 的磁鐵貼在頂點 $i$ 上。因此，磁鐵上的數字形成了一個排列 $p = [p_1, p_2, \dots, p_n]$。

Batyr 考慮子集 $S_{l,r} = \{i : l \le p_i \le r\}$，這些子集由磁鐵數字在 $l$ 到 $r$ 範圍內（$1 \le l \le r \le n$）的頂點組成。與此相關，他對函數 $g(p)$ 感興趣——即所有 $l$ 和 $r$ 對的 $f(S_{l,r})$ 之和。

但 Batyr 研究的關鍵問題是分析排列 $p$ 在微小修改下 $g(p)$ 的行為。他提出了 $q$ 個修改查詢：第 $j$ 個查詢表示交換貼在第 $c_j$ 條邊兩端頂點上的磁鐵。這些修改是累加的：在應用第 $j$ 個修改時，會考慮前 $j - 1$ 次修改的影響。

作為 Batyr 的研究助理，你再次被分配處理這些枯燥的工作。你需要計算在任何修改之前以及每次修改排列 $p$ 之後的 $g(p)$ 值。

輸入格式

第一行包含兩個整數 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分別代表樹的頂點數和修改查詢的次數。

第二行包含 $n$ 個唯一的整數 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，代表貼在每個頂點上的磁鐵數字。

接下來的 $n-1$ 行包含兩個整數 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，描述樹的第 $i$ 條邊。

最後 $q$ 行描述查詢。每行包含一個整數 $c_i$ ($1 \le c_i \le n - 1$)，表示交換貼在頂點 $a_{c_i}$ 和 $b_{c_i}$ 上的磁鐵。

輸出格式

第一行輸出必須包含 $g(p)$ 的值——即所有 $l$ 和 $r$ 對的 $f(S_{l,r})$ 之和。

然後對於每個查詢，在第 $i$ 行輸出交換頂點 $a_{c_i}$ 和 $b_{c_i}$ 之間的磁鐵後 $g(p)$ 的值。

子任務

本題包含 8 個子任務，滿足以下要求：

1. 本敘述中的測試資料。價值 0 分。
2. $n \le 1000, q = 0$。保證對於所有 $i$ ($1 \le i < n$)，$a_i = i, b_i = i + 1$。價值 9 分。
3. $n \le 10^5, q = 0$。保證對於所有 $i$ ($1 \le i < n$)，$a_i = 1, b_i = i + 1$。價值 10 分。
4. $n \le 10^5, q = 0$。保證對於所有 $i$ ($1 \le i < n$)，$a_i = i, b_i = i + 1$。價值 11 分。
5. $n \le 1000, q = 0$。價值 16 分。
6. $n, q \le 10^5$。保證對於所有 $i$ ($1 \le i < n$)，$a_i = i, b_i = i + 1$。價值 16 分。
7. $n \le 10^5, q = 0$。價值 20 分。
8. 原始問題限制。價值 18 分。

範例

輸入 1

3 1
3 2 1
1 2
2 3
1

輸出 1

10
11

說明

讓我們考慮上面的範例。最初 $p = [3, 2, 1]$。

1. $S_{1,1} = \{3\}$ $f(S_{1,1})$ 是包含 $S_{1,1}$ 中所有頂點的連通子圖的最小大小 $f(S_{1,1}) = 1$
2. $S_{1,2} = \{2, 3\}; f(S_{1,2}) = 2$
3. $S_{1,3} = \{1, 2, 3\}; f(S_{1,3}) = 3$
4. $S_{2,2} = \{2\}; f(S_{2,2}) = 1$
5. $S_{2,3} = \{1, 2\}; f(S_{2,3}) = 2$
6. $S_{3,3} = \{1\}; f(S_{3,3}) = 1$

$g(p) = 1 + 2 + 3 + 1 + 2 + 1 = 10$。

在第一次修改後，第 1 條邊兩端的磁鐵被交換。現在 $p$ 等於 $[2, 3, 1]$。

1. $S_{1,1} = \{3\}; f(S_{1,1}) = 1$
2. $S_{1,2} = \{1, 3\}; f(S_{1,2}) = 3$
3. $S_{1,3} = \{1, 2, 3\}; f(S_{1,3}) = 3$
4. $S_{2,2} = \{1\}; f(S_{2,2}) = 1$
5. $S_{2,3} = \{1, 2\}; f(S_{2,3}) = 2$
6. $S_{3,3} = \{2\}; f(S_{3,3}) = 1$

$g(p) = 1 + 3 + 3 + 1 + 2 + 1 = 11$。