Contexte

Pour laisser un souvenir unique du dixième anniversaire, Xiao T et Xiao S ont installé une grande installation d'art interactif appelée « Photo » dans le hall principal.

Cette installation est composée de nombreux nœuds d'image en suspension, reliés par des faisceaux lumineux formant une structure arborescente, chaque nœud étant équipé d'un filtre de couleur différente. En arrivant devant la console, vous découvrez qu'il est possible d'interagir librement avec le système : à chaque réglage des paramètres, le système n'active temporairement que les faisceaux dont les numéros se situent dans un intervalle spécifique, ce qui fragmente le réseau initial en plusieurs sous-zones connexes indépendantes.

De manière ingénieuse, des interférences optiques se produisent entre les nœuds possédant le même type de filtre au sein d'une même sous-zone connexe : lorsqu'une couleur de filtre apparaît un nombre pair de fois dans cette sous-zone, sa lumière s'annule et devient invisible ; lorsqu'elle apparaît un nombre impair de fois, elle se concentre en une couleur clairement visible.

La fragmentation et la recomposition de ces jeux d'ombre et de lumière sont fascinantes, et vous vous intéressez vivement aux changements structurels qui s'y cachent : lors de chaque activation locale, combien de types de filtres visibles sont contenus dans l'ensemble des zones connexes fragmentées ?

Description

Le dispositif « Photo » peut être modélisé comme un arbre contenant $n$ nœuds, chaque nœud représentant un nœud d'image, et la couleur du filtre du nœud $i$ ($1 \le i \le n$) est $c_i$. Il y a $n-1$ faisceaux lumineux reliant les nœuds, numérotés séquentiellement de $1$ à $n-1$.

Au cours de votre exploration, vous avez enregistré les données de $m$ tests d'effets dynamiques. Pour chaque test, vous spécifiez un intervalle de numéros de faisceaux $[l, r]$. En supposant que seuls les faisceaux dont les numéros tombent dans cet intervalle sont activés (les autres faisceaux dont les numéros ne sont pas dans cet intervalle sont déconnectés), le réseau complet initial se divise en plusieurs composantes connexes indépendantes.

Pour analyser plus en profondeur les changements, vous devez calculer pour chaque test : la somme du nombre de types de filtres visibles (c'est-à-dire les couleurs de filtre apparaissant un nombre impair de fois) contenus dans chaque composante connexe.

Entrée

La première ligne de l'entrée contient deux entiers positifs $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$), représentant respectivement le nombre de nœuds d'image et le nombre de tests.

La deuxième ligne contient $n$ entiers positifs $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), représentant la couleur du filtre de chaque nœud d'image.

Les $n-1$ lignes suivantes, la $i$-ième ligne ($1 \le i \le n-1$) contient deux entiers positifs $u_i, v_i$ ($1 \le u_i, v_i \le n$), représentant les deux nœuds connectés par le faisceau numéro $i$.

Les $m$ lignes suivantes, chaque ligne contient deux entiers positifs $l, r$ ($1 \le l \le r \le n-1$), représentant l'intervalle de numéros de faisceaux pour un test.

Sortie

Affichez $m$ lignes, chacune contenant un entier non négatif, représentant la somme du nombre de types de filtres visibles contenus dans chaque composante connexe pour chaque test.

Exemples

Entrée 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

Sortie 1

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