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
n,m= map(int,sys.stdin.readline().split())
a=(input()).split()
class node:
    def __init__(self,data,color):
        self._data=data
        self._color=color
        self._parent=-1
        self._tol={}

def search(h,t,x,d1):
    if h==t:
        if(d1[h][1]>x-1):
            return(h+1)
    elif(h==0)and(d1[h][1]>=x):
        return(h)
    else:
        midh=(h+t)//2
        midt=midh+1
        if(d1[midh][1]<x)and(d1[midt][1]>x-1):
            return(midh+1)
            
        if(d1[midh][1]<=x-1)and(d1[midt][1]<=x-1):
            if midt<=t:
                return(search(midt,t,x,d1))
        if(d1[midh][1]>x-1)and(d1[midt][1]>x-1):
            if midh>=h:
                return(search(h,midh,x,d1))
tree=[]
leaf=[set(),set()]
for i in range(n):
    tree.append(node(i,a[i]))
    leaf[0].add(i)
    tree[i]._tol[a[i]]=1
for i in range(n-1):
    x,y= map(int,sys.stdin.readline().split())
    x-=1
    y-=1
    tree[y]._parent=x
    if a[x]!='0':
        leaf[0].remove(x)
        a[x]='0'
h=0
while len(leaf[h])!=0:
    leaf[1-h].clear()
    for i in leaf[h]:
        for c in tree[i]._tol:
            if c in tree[tree[i]._parent]._tol:
                tree[tree[i]._parent]._tol[c]+=tree[i]._tol[c]
            else:
                tree[tree[i]._parent]._tol[c]=tree[i]._tol[c]
            if tree[i]._parent!=0:
                leaf[1-h].add(tree[i]._parent)
    h=1-h
for i in range(m):
    v,k= map(int,sys.stdin.readline().split())
    d=dict()
    v-=1
    d=tree[v]._tol
    d1=sorted(d.items(),key=lambda d:d[1])
    l=len(d1)
    if search(0,l-1,k,d1)!=None:
        print(l-search(0,l-1,k,d1))
    else:
        print(0)