Batyr zainteresował się ostatnio badaniem drzew. Nie jest jednak dendrologiem, więc zamiast prawdziwych drzew bada właściwości grafów spójnych o $n$ wierzchołkach i $n-1$ krawędziach.

Załóżmy, że $T$ jest nieskierowanym drzewem o $n$ ponumerowanych wierzchołkach. Batyr opisał funkcję $f(S)$: minimalny rozmiar (liczbę węzłów) spójnego podgrafu drzewa $T$, który zawiera wszystkie wierzchołki ze zbioru $S$, gdzie $S$ jest dowolnym podzbiorem wierzchołków $T$. Innymi słowy, wyobraźmy sobie usunięcie maksymalnej liczby wierzchołków z $T$ tak, aby wszystkie wierzchołki ze zbioru $S$ pozostały połączone. Rozmiar powstałego drzewa będzie równy $f(S)$.

Jako zaawansowany badacz, Batyr nie zadowala się takimi trywialnościami. Wybrał już drzewo $T$ i narysował je na tablicy. Następnie do każdego wierzchołka na tablicy przyczepił mały magnes z unikalnym numerem od $1$ do $n$. Indeks wierzchołka i numer na magnesie mogą się różnić: magnes z numerem $p_i$ jest przyczepiony do wierzchołka $i$. Zatem numery na magnesach tworzą permutację $p = [p_1, p_2, \dots, p_n]$.

Batyr rozważa podzbiory $S_{l,r} = \{i : l \le p_i \le r\}$, które składają się z wierzchołków posiadających magnesy z numerami w zakresie od $l$ do $r$ ($1 \le l \le r \le n$). W związku z tym interesuje go funkcja $g(p)$ — suma $f(S_{l,r})$ po wszystkich parach $l$ i $r$.

Kluczowym pytaniem w badaniach Batyra jest analiza zachowania $g(p)$ przy niewielkich modyfikacjach permutacji $p$. Wymyślił $q$ zapytań modyfikujących: $j$-te zapytanie oznacza zamianę magnesów przyczepionych do końcowych wierzchołków $c_j$-tej krawędzi. Modyfikacje są składane: efekt pierwszych $j-1$ modyfikacji jest uwzględniany przy stosowaniu $j$-tej.

Jako asystent badawczy Batyra, po raz kolejny zostałeś oddelegowany do nudnej pracy. Musisz obliczyć wartości $g(p)$ przed każdą modyfikacją oraz po każdej z nich.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $q$ ($1 \le n, q \le 10^5$) — liczbę wierzchołków w drzewie oraz liczbę zapytań modyfikujących.

Druga linia zawiera $n$ unikalnych liczb całkowitych $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — numery na magnesach przyczepionych do każdego wierzchołka.

Kolejne $n-1$ linii zawiera dwie liczby całkowite $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) opisujące $i$-tą krawędź drzewa.

Ostatnie $q$ linii opisuje zapytania. Każda linia zawiera liczbę całkowitą $c_i$ ($1 \le c_i \le n-1$), oznaczającą zamianę magnesów przyczepionych do wierzchołków $a_{c_i}$ oraz $b_{c_i}$.

Wyjście

Pierwsza linia wyjścia musi zawierać wartość $g(p)$ — sumę $f(S_{l,r})$ po wszystkich parach $l$ i $r$.

Następnie dla każdego zapytania wypisz w $i$-tej linii wartość $g(p)$ po zamianie magnesów między wierzchołkami $a_{c_i}$ oraz $b_{c_i}$.

Podzadania

Problem zawiera 8 podzadań, które spełniają następujące wymagania:

1. Testy z treści zadania. Wartość 0 punktów.
2. $n \le 1000, q = 0$. Gwarantowane, że $a_i = i, b_i = i + 1$ dla wszystkich $i$ ($1 \le i < n$). Wartość 9 punktów.
3. $n \le 10^5, q = 0$. Gwarantowane, że $a_i = 1, b_i = i + 1$ dla wszystkich $i$ ($1 \le i < n$). Wartość 10 punktów.
4. $n \le 10^5, q = 0$. Gwarantowane, że $a_i = i, b_i = i + 1$ dla wszystkich $i$ ($1 \le i < n$). Wartość 11 punktów.
5. $n \le 1000, q = 0$. Wartość 16 punktów.
6. $n, q \le 10^5$. Gwarantowane, że $a_i = i, b_i = i + 1$ dla wszystkich $i$ ($1 \le i < n$). Wartość 16 punktów.
7. $n \le 10^5, q = 0$. Wartość 20 punktów.
8. Oryginalne ograniczenia zadania. Wartość 18 punktów.

Przykład

Wejście 1

3 1
3 2 1
1 2
2 3
1

Wyjście 1

10
11

Uwagi

Rozważmy powyższy przykład. Początkowo $p = [3, 2, 1]$.

1. $S_{1,1} = \{3\}$ $f(S_{1,1})$ to minimalny rozmiar spójnego podgrafu zawierającego wszystkie wierzchołki z $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$.

Po pierwszej modyfikacji magnesy na końcach 1-szej krawędzi zostają zamienione. Teraz $p$ jest równe $[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$.