題目背景

為了給大家留下獨特的十週年紀念，小 T 和小 S 在主會場中布置了一個大型的交互藝術裝置「幻光留影」。

這個裝置由許多懸浮的影像結點組成，通過光束連接成了一棵樹的形態，並為每個結點配置了不同顏色的光影濾鏡。你來到了控制台前，發現這裡可以自由互動：每當調節控制台上的參數，系統會臨時只激活特定編號區間內的光束，這會讓原本完整的留影網絡分裂成若干個獨立的連通子區域。

充滿巧思的是，同一連通子區域中帶有同種濾鏡的結點之間會發生光學干涉：當某種顏色的濾鏡在該連通子區域內出現了偶數次時，它們的光芒將相互抵消變得不可見；而當其出現次數為奇數時，則會匯聚成清晰可見的色彩。

光影的破碎與重組十分迷人，你對其中隱藏的結構變化產生了濃厚的興趣：在每一次這樣的局部激活下，所有分裂出來的連通區域中，各自包含了多少種不同的可見濾鏡呢？

題目敘述

幻光留影裝置可抽象為一棵包含 $n$ 個結點的樹，每個結點代表一個影像結點，結點 $i$ ($1 \le i \le n$) 的濾鏡顏色為 $c_i$。連接結點的光束共有 $n-1$ 條，並依次編號為 $1$ 到 $n-1$。

在你嘗試探索規律的過程中，記錄了 $m$ 次動態效果測試的數據。對於每一次測試，你指定了一個光束的編號區間 $[l, r]$。假設此時只激活編號落在該區間內的光束（斷開編號不在該區間內的其他光束），原先連通的整個網絡便會分裂成若干個獨立的連通塊。

為了更深入地分析其中的變化，你需要針對每一次測試計算出：所有連通塊中，各自包含的「可見濾鏡」（即出現次數為奇數的濾鏡顏色）種類數的總和。

輸入格式

輸入的第一行包含兩個正整數 $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$)，分別表示影像結點的數量與測試次數。

輸入的第二行包含 $n$ 個正整數 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$)，分別表示每個影像結點的濾鏡顏色。

接下來 $n-1$ 行，第 $i$ ($1 \le i \le n-1$) 行包含兩個正整數 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示編號為 $i$ 的光束連接的兩個結點。

接下來 $m$ 行，每行包含兩個正整數 $l, r$ ($1 \le l \le r \le n-1$)，表示一次測試的光束編號區間。

輸出格式

輸出 $m$ 行，每行一個非負整數，依次表示每次測試中所有獨立連通塊各自包含的可見濾鏡種類數的總和。

範例

輸入格式 1

12 13
2 4 1 2 3 4 2 4 3 3 3 6
3 5
9 1
5 11
4 9
1 12
2 1
10 8
11 10
8 4
6 11
7 6
1 3
2 2
6 6
9 11
6 11
1 4
8 10
1 11
5 10
4 7
1 10
6 8
11 11

輸出格式 1

10
12
12
12
6
8
10
4
8
12
4
10
12