Batyr는 최근 나무(tree) 연구에 빠졌습니다. 하지만 그는 수목학자가 아니기 때문에, 실제 나무 대신 $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는 자석에 적힌 번호가 $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$번째 수정이 적용될 때 $1$부터 $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$개의 줄에는 트리의 $i$번째 간선을 설명하는 두 정수 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)가 주어집니다.

마지막 $q$개의 줄은 쿼리를 설명합니다. 각 줄에는 정점 $a_{c_i}$와 $b_{c_i}$에 붙은 자석을 교환함을 의미하는 정수 $c_i$ ($1 \le c_i \le n-1$)가 주어집니다.

출력

첫 번째 줄에는 모든 $l$과 $r$의 쌍에 대한 $f(S_{l,r})$의 합인 $g(p)$의 값을 출력해야 합니다.

그 후 각 쿼리에 대해, 정점 $a_{c_i}$와 $b_{c_i}$ 사이의 자석을 교환한 후의 $g(p)$ 값을 $i$번째 줄에 출력하십시오.

서브태스크

이 문제는 다음 요구사항을 만족하는 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$.