Batyrは最近、木の研究に夢中になっています。しかし、彼は樹木学者ではないため、実際の木ではなく、$n$ 頂点 $n-1$ 辺からなる連結グラフの性質を研究しています。

$T$ を $n$ 個の頂点に番号が付けられた無向木とします。Batyrは関数 $f(S)$ を次のように定義しました。$S$ を $T$ の頂点の任意の空でない部分集合としたとき、$f(S)$ は $S$ に含まれるすべての頂点を含む $T$ の連結部分グラフの最小サイズ（ノード数）です。言い換えれば、$S$ に含まれるすべての頂点が連結を保つように $T$ から頂点を最大数取り除いたとき、残った木のサイズが $f(S)$ となります。

先進的な研究者であるBatyrは、このような単純なことでは満足しません。彼はすでに木 $T$ を選び、ホワイトボードに描きました。そして、1から $n$ までの固有の番号が書かれた小さな磁石を、ボード上のすべての頂点に取り付けました。頂点のインデックスとそれに取り付けられた磁石の番号は異なる場合があります。番号 $p_i$ の磁石が頂点 $i$ に取り付けられているとします。したがって、磁石の番号は順列 $p = [p_1, p_2, \dots, p_n]$ を形成します。

Batyrは、$l$ から $r$ までの範囲の番号が書かれた磁石を持つ頂点からなる部分集合 $S_{l,r} = \{i : l \le p_i \le r\}$ を考えます（$1 \le l \le r \le n$）。これに関連して、彼はすべての $l$ と $r$ のペアに対する $f(S_{l,r})$ の総和である関数 $g(p)$ に興味を持っています。

しかし、Batyrの研究の核心的な問いは、順列 $p$ の小さな変更に対する $g(p)$ の挙動を分析することです。彼は $q$ 個の変更クエリを考案しました。$j$ 番目のクエリは、$c_j$ 番目の辺の両端の頂点に取り付けられた磁石を入れ替えることを意味します。この変更は累積されます。つまり、$j$ 番目の変更を行う際には、最初の $j-1$ 回の変更の影響が考慮されます。

Batyrの研究助手として、あなたは再び退屈な作業を任されました。順列 $p$ の変更前、および各変更後の $g(p)$ の値を計算してください。

入力

入力の最初の行には、2つの整数 $n$ と $q$ ($1 \le n, q \le 10^5$) が含まれます。これは木の頂点数と変更クエリの数です。

2行目には、$n$ 個の固有の整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) が含まれます。これは各頂点に取り付けられた磁石の番号です。

続く $n-1$ 行には、2つの整数 $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$。