Distinct Colors after Removing Specific Ancestors

We are given a tree with n nodes rooted at 1. Each node i has a color c_i. Let \(P(u,v)\) denote the sequence of nodes on the unique simple path from node \(u\) to node \(v\) (including both \(u\) and \(v\)). Let \(dep_u\) be the depth of node \(u\) (with \(dep_1=0\)) when the tree is rooted at 1. Also, \(\operatorname{LCA}(u,v)\) denotes the lowest common ancestor of \(u\) and \(v\) in the tree (with root 1).

For a node \(x\) and an integer \(k\), consider the path \(P(x,1)\) from \(x\) to the root. Remove from \(P(x,1)\) all nodes \(y\) satisfying \[ dep_y \equiv dep_x \pmod{k}. \] After this removal, let \(S\) be the set of all nodes \(z\) with \(dep_z \le dep_x\) that remain in the tree. The task is to answer m independent queries. Each query gives two integers \(x\) and \(k\), and you must output the number of distinct colors among nodes in \(S\).

Note: Each query is independent – that is, the removals in one query do not affect later queries.

inputFormat

The input begins with two integers n and m, the number of nodes and the number of queries.

The next line contains n integers, where the i-th integer is c_i, the color of node i.

Then follow n-1 lines, each with two integers u and v indicating that there is an edge between nodes u and v (the tree is undirected and rooted at 1).

Finally, there are m lines, each containing two integers x and k describing a query.

outputFormat

For each query, output one integer – the number of distinct colors among nodes with depth no more than dep_x after removing all nodes \(y\) in \(P(x,1)\) satisfying \(dep_y \equiv dep_x \pmod{k}\). Print each answer on a separate line.

sample

5 3
1 2 3 2 1
1 2
1 3
2 4
2 5
4 2
5 1
3 2

3
2
2