You have a rooted tree consisting of *n* vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to *n*. Then we represent the color of vertex *v* as *c*<sub class="lower-index">*v*</sub>. The tree root is a vertex with number 1.

In this problem you need to answer to *m* queries. Each query is described by two integers *v*<sub class="lower-index">*j*</sub>, *k*<sub class="lower-index">*j*</sub>. The answer to query *v*<sub class="lower-index">*j*</sub>, *k*<sub class="lower-index">*j*</sub> is the number of such colors of vertices *x*, that the subtree of vertex *v*<sub class="lower-index">*j*</sub> contains at least *k*<sub class="lower-index">*j*</sub> vertices of color *x*.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).
The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>; 1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>). The next line contains a sequence of integers *c*<sub class="lower-index">1</sub>, *c*<sub class="lower-index">2</sub>, ..., *c*<sub class="lower-index">*n*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>). The next *n* - 1 lines contain the edges of the tree. The *i*-th line contains the numbers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*; *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>) — the vertices connected by an edge of the tree.

Next *m* lines contain the queries. The *j*-th line contains two integers *v*<sub class="lower-index">*j*</sub>, *k*<sub class="lower-index">*j*</sub> (1 ≤ *v*<sub class="lower-index">*j*</sub> ≤ *n*; 1 ≤ *k*<sub class="lower-index">*j*</sub> ≤ 10<sup class="upper-index">5</sup>).
import sys 
sys.setrecursionlimit(200000)
input = sys.stdin.readline 
n, m = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    g[u].append(v)
    g[v].append(u)
root = 1
queries = [[] for _ in range(n)]
answers = [0] * m 
for i in range(m):
    v, k = map(int, input().split())
    queries[v-1].append((k,i))

class Data:
    def __init__(self):
        self.postcnt = [0, 0]
        self.M = {}
        self.tot = 0
    def insert(self, x):
        if x in self.M:
            self.M[x] += 1
            if self.M[x] >= len(self.postcnt):
                self.postcnt.append(0)
            self.postcnt[self.M[x]] += 1
        else:
            self.M[x] = 1
            self.postcnt[1] += 1
    def query(self, i):
        if i >= len(self.postcnt):
            return 0
        else:
            return self.postcnt[i]
    
f = [Data() for _ in range(n)]
sz = [1] * n
root = 0
def dfs(u, last):
    global f, sz, answers
    # dfs and get heavy
    heavy = -1
    for v in g[u]:
        if v != last:
            dfs(v, u)
            sz[u] += sz[v]
            if heavy == -1 or sz[v] > sz[heavy]:
                heavy = v
    # init or update f
    if sz[u] == 1:
        f[u].insert(c[u])
    else:
        f[u] = f[heavy]
        # print(u, heavy, f[u],f[heavy])
        f[u].insert(c[u])
        for v in g[u]:
            if v != last and v != heavy:
                for key in f[v].M:
                    for _ in range(f[v].M[key]):
                        f[u].insert(key)
    # handle queries
    for k, i in queries[u]:
        answers[i] = f[u].query(k)
dfs(root, -1)
for x in answers:
    print(x)