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 logging

qwe = 1000005
siz = [0 for i in range(qwe)]
son = [0 for i in range(qwe)]
tree = [0 for i in range(qwe)]
cnt = [0 for i in range(qwe)]
L = [0 for i in range(qwe)]
id = [0 for i in range(qwe)]
e = [[] for i in range(qwe)]
ans = [0 for i in range(qwe)]
a = [0]
q = [[] for i in range(qwe)]
dfn = 0


def change(x, k):
    while x <= qwe - 1:
        tree[x] += k
        x += (x & (-x))


def ask(x):
    ans = 0
    while x > 0:
        ans += tree[x]
        x -= (x & (-x))
    return ans


def add(x):
    if cnt[a[x]] != 0:
        change(cnt[a[x]], -1)
    cnt[a[x]] += 1
    change(cnt[a[x]], 1)


def dl(x):
    change(cnt[a[x]], -1)
    cnt[a[x]] -= 1
    if cnt[a[x]] != 0:
        change(cnt[a[x]], 1)


def dfs(u, fa):
    global siz, dfn, L
    siz[u] = 1
    dfn += 1
    L[u] = dfn
    id[dfn] = u
    for v in e[u]:
        if v == fa:
            continue
        dfs(v, u)
        siz[u] += siz[v]
        if siz[v] > siz[son[u]]:
            son[u] = v


def dfs2(u, fa, k):
    for v in e[u]:
        if v == fa or v == son[u]:
            continue
        dfs2(v, u, 0)
    if son[u] != 0:
        dfs2(son[u], u, 1)
    for v in e[u]:
        if v == fa or v == son[u]:
            continue
        for i in range(L[v], L[v] + siz[v]):
            add(id[i])
    add(u)
    for j in q[u]:
        ans[j[1]] = ask(qwe - 1) - ask(j[0] - 1)
    if k == 0:
        for i in range(L[u], L[u] + siz[u]):
            dl (id[i])


if __name__ == "__main__":
    a = input().split()
    n = int(a[0])
    m = int(a[1])
    a=[0]
    k=input().split()
    for i in range(1,n+1):
        a.append(int(k[i-1]))
    for i in range(1, n):
        u = input().split()
        v = int(u[1])
        u = int(u[0])
        e[u].append(v)
        e[v].append(u)
    for i in range(1, m + 1):
        k = input().split()
        v = int(k[0])
        k = int(k[1])
        q[v].append([k, i])
    dfs(1, 0)
    dfs2(1, 0, 0)
    for i in range(1, m + 1):
        print(ans[i])
