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>).
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
#define rs resize
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

const ll N = 100009;
ll n,i,a,b,m,T;
vector<vi> adj;
vector<vector<ii> > q;
ll st[N],ft[N],sz[N],col[N],ver[N],bit[N],cnt[N],ans[N];
void Dfs(ll v,ll p)
{
    ver[T] = v;
    st[v] = T++;
    sz[v] = 1;
    for(auto &it: adj[v]) if(it != p){
        Dfs(it,v);
        sz[v] += sz[it];
    }
    ft[v] = T;
}
void up(ll i,ll val)
{
    while(i < N){
        bit[i] += val;
        i += i&(-i);
    }
}
ll query(ll i)
{
    ll s = 0;
    while(i > 0){
        s += bit[i];
        i -= i&(-i);
    }
    return s;
}
void dfs(ll v,ll p,ll keep)
{
    ll mx = -1,bg = -1;
    for(auto &it: adj[v]) if(it != p and mx < sz[it]){
        mx = sz[it];
        bg = it;
    }
    for(auto &it: adj[v]) if(it != p and it != bg){
        dfs(it,v,0);
    }
    if(bg != -1)
        dfs(bg,v,1);
    for(auto &it: adj[v]) if(it != p and it != bg){
        for(ll p = st[it];p < ft[it];p++){
            ll d = cnt[col[ver[p]]]++;
            if(d != 0)
                up(d,-1);
            up(d + 1,1);
        }
    }
    
    ll d = cnt[col[v]]++;
    if(d != 0)
        up(d,-1);
    up(d + 1,1);
    
    
    for(auto &it: q[v]){
        ans[it.se] = query(N) - query(it.f - 1);
    }
    
    if(keep == 0) for(ll p = st[v];p < ft[v];p++){
        ll d = --cnt[col[ver[p]]];
        if(d != 0)
            up(d,1);
        up(d + 1,-1);
    }
}
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    rep(i,0,n) cin>>col[i];
    adj.rs(n); q.rs(n);
    rep(i,1,n){
        cin>>a>>b;
        a--; b--;
        adj[a].pb(b); adj[b].pb(a);
    }
    rep(i,0,m){
        cin>>a>>b;
        q[a - 1].pb({b,i});
    }
    Dfs(0,-1);
    dfs(0,-1,0);
    rep(i,0,m) 
        cout<<ans[i]<<endl;
    return 0;
}