Batyr s'est récemment mis à étudier les arbres. Mais n'étant pas dendrologue, au lieu d'arbres réels, il étudie les propriétés de graphes connexes à $n$ sommets et $n - 1$ arêtes.

Supposons que $T$ soit un arbre non orienté sur $n$ sommets indexés. Batyr a décrit une fonction $f(S)$ : la taille minimale (le nombre de nœuds) d'un sous-graphe connexe de $T$ qui contient tous les sommets de $S$, où $S$ est un sous-ensemble arbitraire de sommets de $T$. En d'autres termes, imaginez que l'on supprime le nombre maximal de sommets dans $T$ de telle sorte que tous les sommets de $S$ restent connectés. La taille de l'arbre résultant serait égale à $f(S)$.

En tant que chercheur avancé, Batyr ne se satisfait pas de telles trivialités. Il a déjà choisi un arbre $T$ et l'a dessiné sur un tableau blanc. Il a ensuite attaché un petit aimant portant un numéro unique de $1$ à $n$ à chaque sommet du tableau. L'indice d'un sommet et le numéro sur l'aimant qui y est attaché peuvent différer : un aimant portant le numéro $p_i$ est attaché au sommet $i$. Par conséquent, les numéros sur les aimants forment une permutation $p = [p_1, p_2, \dots, p_n]$.

Batyr considère les sous-ensembles $S_{l,r} = \{i : l \le p_i \le r\}$ qui consistent en des sommets ayant un numéro sur l'aimant attaché compris entre $l$ et $r$ ($1 \le l \le r \le n$). En lien avec ceux-ci, il s'intéresse à la fonction $g(p)$ — la somme de $f(S_{l,r})$ sur toutes les paires de $l$ et $r$.

Mais la question clé de la recherche de Batyr est d'analyser le comportement de $g(p)$ sous de petites modifications de la permutation $p$. Il a imaginé $q$ requêtes de modification : la $j$-ième requête désigne un échange des aimants attachés aux sommets extrémités de la $c_j$-ième arête. Les modifications se cumulent : l'effet des $j - 1$ premières modifications est pris en compte lors de l'application de la $j$-ième.

En tant qu'assistant de recherche de Batyr, vous êtes une fois de plus chargé des tâches fastidieuses. Vous devez calculer les valeurs de $g(p)$ avant toute modification et après chaque modification de la permutation $p$.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $q$ ($1 \le n, q \le 10^5$) — le nombre de sommets dans l'arbre et le nombre de requêtes de modification.

La deuxième ligne contient $n$ entiers uniques $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — les numéros sur les aimants attachés à chaque sommet.

Les $n-1$ lignes suivantes contiennent deux entiers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) décrivant la $i$-ième arête de l'arbre.

Les $q$ lignes finales décrivent les requêtes. Chaque ligne contient un entier $c_i$ ($1 \le c_i \le n - 1$), désignant un échange des aimants attachés aux sommets $a_{c_i}$ et $b_{c_i}$.

Sortie

La première ligne de la sortie doit contenir la valeur de $g(p)$ — la somme de $f(S_{l,r})$ sur toutes les paires de $l$ et $r$.

Ensuite, pour chaque requête, imprimez sur la $i$-ième ligne la valeur de $g(p)$ après avoir échangé les aimants entre les sommets $a_{c_i}$ et $b_{c_i}$.

Sous-tâches

Ce problème contient 8 sous-tâches, qui répondent aux exigences suivantes :

1. Tests de cet énoncé. Vaut 0 point.
2. $n \le 1000, q = 0$. Il est garanti que $a_i = i, b_i = i + 1$ pour tout $i$ ($1 \le i < n$). Vaut 9 points.
3. $n \le 10^5, q = 0$. Il est garanti que $a_i = 1, b_i = i + 1$ pour tout $i$ ($1 \le i < n$). Vaut 10 points.
4. $n \le 10^5, q = 0$. Il est garanti que $a_i = i, b_i = i + 1$ pour tout $i$ ($1 \le i < n$). Vaut 11 points.
5. $n \le 1000, q = 0$. Vaut 16 points.
6. $n, q \le 10^5$. Il est garanti que $a_i = i, b_i = i + 1$ pour tout $i$ ($1 \le i < n$). Vaut 16 points.
7. $n \le 10^5, q = 0$. Vaut 20 points.
8. Contraintes originales du problème. Vaut 18 points.

Exemples

Entrée 1

3 1
3 2 1
1 2
2 3
1

Sortie 1

10
11

Remarque

Considérons l'exemple ci-dessus. Initialement $p = [3, 2, 1]$.

1. $S_{1,1} = \{3\}$ $f(S_{1,1})$ est la taille minimale d'un sous-graphe connexe qui contient tous les sommets dans $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$.

Après la première modification, les aimants sur les extrémités de la 1-ère arête sont échangés. Maintenant $p$ est égal à $[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$.