Batyr gần đây bắt đầu nghiên cứu về cây. Tuy nhiên, anh ấy không phải là một nhà nghiên cứu cây cối, vì vậy thay vì các loại cây thực thụ, anh ấy nghiên cứu các tính chất của đồ thị liên thông có $n$ đỉnh và $n - 1$ cạnh.

Giả sử $T$ là một cây vô hướng trên $n$ đỉnh được đánh chỉ số. Batyr đã mô tả một hàm $f(S)$: kích thước tối thiểu (số lượng nút) của một đồ thị con liên thông của $T$ chứa tất cả các đỉnh trong $S$, trong đó $S$ là một tập con tùy ý các đỉnh của $T$. Nói cách khác, hãy tưởng tượng việc xóa đi số lượng đỉnh tối đa trong $T$ sao cho tất cả các đỉnh từ $S$ vẫn liên thông với nhau. Kích thước của cây thu được sẽ bằng $f(S)$.

Là một nhà nghiên cứu cấp cao, Batyr không hài lòng với những điều tầm thường như vậy. Anh ấy đã chọn một cái cây $T$ và vẽ nó lên bảng. Sau đó, anh ấy gắn một nam châm với một số duy nhất từ $1$ đến $n$ vào mỗi đỉnh trên bảng. Chỉ số của một đỉnh và số trên nam châm gắn vào nó có thể khác nhau: một nam châm với số $p_i$ được gắn vào đỉnh $i$. Do đó, các số trên các nam châm tạo thành một hoán vị $p = [p_1, p_2, \dots, p_n]$.

Batyr xét các tập con $S_{l,r} = \{i : l \le p_i \le r\}$ bao gồm các đỉnh có số trên nam châm gắn vào nằm trong khoảng từ $l$ đến $r$ ($1 \le l \le r \le n$). Liên quan đến các tập này, anh ấy quan tâm đến hàm $g(p)$ — tổng của $f(S_{l,r})$ trên tất cả các cặp $l$ và $r$.

Nhưng câu hỏi chính trong nghiên cứu của Batyr là phân tích hành vi của $g(p)$ dưới các sửa đổi nhỏ của hoán vị $p$. Anh ấy đã đưa ra $q$ truy vấn sửa đổi: truy vấn thứ $j$ biểu thị việc hoán đổi các nam châm gắn vào các đỉnh đầu mút của cạnh thứ $c_j$. Các sửa đổi có tính tích lũy: hiệu ứng của $j - 1$ sửa đổi đầu tiên được tính đến khi áp dụng sửa đổi thứ $j$.

Với tư cách là trợ lý nghiên cứu của Batyr, bạn lại được giao những công việc nhàm chán. Bạn cần tính toán các giá trị của $g(p)$ trước bất kỳ sửa đổi nào và sau mỗi lần sửa đổi hoán vị $p$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $q$ ($1 \le n, q \le 10^5$) — số lượng đỉnh trong cây và số lượng truy vấn sửa đổi.

Dòng thứ hai chứa $n$ số nguyên duy nhất $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — các số trên nam châm gắn vào mỗi đỉnh.

$n-1$ dòng tiếp theo chứa hai số nguyên $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) mô tả cạnh thứ $i$ của cây.

$q$ dòng cuối cùng mô tả các truy vấn. Mỗi dòng chứa một số nguyên $c_i$ ($1 \le c_i \le n - 1$), biểu thị việc hoán đổi các nam châm gắn vào các đỉnh $a_{c_i}$ và $b_{c_i}$.

Dữ liệu ra

Dòng đầu tiên của dữ liệu ra phải chứa giá trị của $g(p)$ — tổng $f(S_{l,r})$ trên tất cả các cặp $l$ và $r$.

Sau đó, với mỗi truy vấn, in ra trên dòng thứ $i$ giá trị của $g(p)$ sau khi hoán đổi các nam châm giữa các đỉnh $a_{c_i}$ và $b_{c_i}$.

Nhiệm vụ con

Bài toán này bao gồm 8 nhiệm vụ con, đáp ứng các yêu cầu sau:

1. Các bài kiểm tra từ đề bài này. Trị giá 0 điểm.
2. $n \le 1000, q = 0$. Đảm bảo $a_i = i, b_i = i + 1$ với mọi $i$ ($1 \le i < n$). Trị giá 9 điểm.
3. $n \le 10^5, q = 0$. Đảm bảo $a_i = 1, b_i = i + 1$ với mọi $i$ ($1 \le i < n$). Trị giá 10 điểm.
4. $n \le 10^5, q = 0$. Đảm bảo $a_i = i, b_i = i + 1$ với mọi $i$ ($1 \le i < n$). Trị giá 11 điểm.
5. $n \le 1000, q = 0$. Trị giá 16 điểm.
6. $n, q \le 10^5$. Đảm bảo $a_i = i, b_i = i + 1$ với mọi $i$ ($1 \le i < n$). Trị giá 16 điểm.
7. $n \le 10^5, q = 0$. Trị giá 20 điểm.
8. Các ràng buộc của bài toán gốc. Trị giá 18 điểm.

Ví dụ

Dữ liệu vào 1

3 1
3 2 1
1 2
2 3
1

Dữ liệu ra 1

10
11

Ghi chú

Hãy xem xét ví dụ trên. Ban đầu $p = [3, 2, 1]$.

1. $S_{1,1} = \{3\}$ $f(S_{1,1})$ là kích thước tối thiểu của một đồ thị con liên thông chứa tất cả các đỉnh trong $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$.

Sau lần sửa đổi đầu tiên, các nam châm trên các đầu mút của cạnh thứ 1 được hoán đổi. Bây giờ $p$ bằng $[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$.