Problem: 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 cv. 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 vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj 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).

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output

Print m integers — the answers to the queries in the order the queries appear in the input.

Examples

Input

8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3


Output

2
2
1
0
1


Input

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


Output

4

Note

A subtree of vertex v in a rooted tree with root r is a set of vertices {u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

Solution (in JAVA):

Solution:

import java.util.*;

import java.io.*;
public class yoyo		
{ 
			 static FastReader sc=new FastReader(); 
			 static long dp[][];
			 static int mod=1000000007;
			 static int max;
			 static long ans;
			 static int block_size;
			 static int n;

			 static int F[];
			 static int col[];

			 static int FF[];
			 static int in[];
			 static int ot[];
			 static int ft[];
			 static int B[];

			 static long bit[];
			 static int timer=1;
			 
			 //static HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
			// static int map[]=new int[300001];
		     public static void main(String[] args)
		    {
			  PrintWriter out=new PrintWriter(System.out);
			  StringBuffer sb=new StringBuffer("");
			 
		  int ttt=1;
		//  ttt =i();
		    outer :while (ttt-- > 0) 
			{
		    	int n=i()+1;
		    	int q=i();
		    	B=input(n-1);
		    	FF=new int[100001];
		    	F=new int[n];
		    	bit=new long[100001];
		    	in=new int[n];
		    	ot=new int[n];
		    	ft=new int[2*n];
		    	col=new int[100001];
		    	ArrayList<Integer> A[]=new ArrayList[n];
	        	for(int i=0;i<A.length;i++) {
	        		A[i]=new ArrayList<Integer>();
	        	}
	        	for(int i=0;i<n-2;i++) {
	        		int a=i();
	        		int b=i();
	        		A[a].add(b);
	        		A[b].add(a);
	        	}
	        	dfs(A, 1, -1);
		    	block_size=600;//(int)Math.sqrt(n-1);
		    	Tri P[]=new Tri[q];
		    	for(int i=0;i<q;i++) {
		    		int a=i();
		    		int b=i();
		    		P[i]=new Tri(in[a],ot[a], i,b);
		    	}
		    	Arrays.sort(P);
		    	long r[]=new long[q];
		    	int l=0,u=-1;
		    	for(int i=0;i<q;i++) {
		    		int a=P[i].x;
		    		int b=P[i].y;
		    		int idx=P[i].z;
		    		int cl=P[i].k;
		    		while(l>a) {
		    			l--;
		    			add(l);
		    		}
		    		while(u<b) {
		    			u++;
		    			add(u);
		    			
		    		}
		    		
		    		
		    		while(u>b) {
		    			remove(u);
		    			u--;
		    		}
		    		while(l<a) {
		    			remove(l);
		    			l++;
		    		}
		    		if(cl>=(n-1)) {
		    			r[idx]=0;
		    			continue;
		    		}
		    		long ans=getans(cl);
		    		r[idx]=ans;
		    		
		    		
		    		
		    	}
		    	for(int i=0;i<q;i++) {
		    		out.println(r[i]);
		    	}
		    	
		    	
		    	
		    	
	        	
			}
		   out.close();
		  // System.out.println(sb.toString());
		   
		   
		   //CHECK FOR N=1                    //CHECK FOR M=0
		    //CHECK FOR N=1                    //CHECK FOR M=0
		   	//CHECK FOR N=1
		   	//CHECK FOR N=1
		   	//CHECK FOR N=1
    }
		     private static void dfs(ArrayList<Integer> [] A, int i, int par) {
					in[i]=timer;
					ft[timer]=i;
					timer++;
					for(int child : A[i]) {
						if(child != par) {
							dfs(A, child, i);
						}
					}
					ot[i]=timer;
					ft[timer]=i;
					timer++;
					
				}
		     static int blk(int u) {

				  int t=(block_size+u-1)/block_size;
				  return t;
		     }

			  private static void remove(int u) {
				  F[ft[u]]--;
					if(F[ft[u]]==1) {
						int c=B[ft[u]-1];
						int tp=col[c];
						col[c]--;
						if(col[c]!=0) {
							FF[col[c]]++;
							bit[blk(col[c])]++;
							//update(col[c], 1);
						}

						FF[tp]--;
						bit[blk(tp)]--;
						//update(tp, -1);
					}
					
				  
				
			}

			private static void add(int u) {
				F[ft[u]]++;
				if(F[ft[u]]==2) {
					int c=B[ft[u]-1];
					int tp=col[c];
					col[c]++;
					if(tp==0) {
						FF[tp+1]++;
					}
					else {
						FF[tp+1]++;
						FF[tp]--;
						//update(tp, -1);
						bit[blk(tp)]--;
					}
					//update(tp+1, 1);
					bit[blk(tp+1)]++;
					
				}
				
				
			}
			static long getans(int k) {
				int lb=blk(k);
				int ub=blk(B.length);
				long sum=0;
				if(lb==ub) {
					for(int i=k;i<=B.length;i++) {
						sum+=FF[i];
					}
					return sum;
				}
				for(int i=k;i<=lb*block_size;i++) {
					sum += FF[i];
				}
					
					for(int i=lb+1;i<ub;i++)
					sum += bit[i];
					
					for(int i=ub*block_size+1;i<=B.length;i++)
					sum += FF[i];
					return sum;
			}

			static class Tri implements Comparable<Tri>
			     {
			    	 int x;
			    	 int y;
			    	 int z;
			    	 int k;
			    	 Tri(int x,int y,int z,int k){
			    		 this.x=x;
			    		 this.y=y;
			    		 this.z=z;
			    		 this.k=k;
			    		 
			    	 }
					@Override
					public int compareTo(Tri o) {
						if(this.x/block_size==o.x/block_size) {
			                if(this.y==o.y)return this.z-o.z;
			                return y-o.y;
			            }
			            return x/block_size-o.x/block_size;
			        }
			     }
			     
			static void update(int i, int x){
				for(; i < bit.length; i += (i&-i))
					bit[i] += x;
			}

			static long sum(int i){
				long ans = 0;
				for(; i > 0; i -= (i&-i))
					ans += bit[i];
				return ans;
			}

		    







static class Pair implements Comparable<Pair>
   {
	   int x;
	   int y;
	  	 Pair(int x,int y){
	  		 this.x=x;
	  		 this.y=y;
	  	 }
	@Override
//	public int compareTo(Pair o) {
//		if(this.x>o.x)
//			return 1;
//		else if(this.x<o.x)
//			return -1;
//		else {
//			if(this.y<o.y)
//				return 1;
//			else if(this.y>o.y)
//				return -1;
//			else
//				return 0;
//		}
//	}
	
	
	public int compareTo(Pair o) {
			if (x > o.x) {
				return 1;
			}
			if (x < o.x) {
				return -1;
			}
			if (y > o.y) {
				return 1;
			}
			if (y < o.y) {
				return -1;
			}
			return 0;
		}
	
 }
static int[] input(int n) {
  	int A[]=new int[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.nextInt();
  	   }
  	   return A;
     }
  static long[] inputL(int n) {
  	long A[]=new long[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.nextLong();
  	   }
  	   return A;
     }
  static String[] inputS(int n) {
  	String A[]=new String[n];
  	   for(int i=0;i<n;i++) {
  		   A[i]=sc.next();
  	   }
  	   return A;
     }
  static long sum(int A[]) {
  	long sum=0;
  	for(int i : A) {
  		sum+=i;
  	}
  	return sum;
  }
  static long sum(long A[]) {
  	long sum=0;
  	for(long i : A) {
  		sum+=i;
  	}
  	return sum;
  }

  static void input(int A[],int B[]) {
  	   for(int i=0;i<A.length;i++) {
  		   A[i]=sc.nextInt();
  		   B[i]=sc.nextInt();
  	   }
  }
  static int[][] input(int n,int m){
  	int A[][]=new int[n][m];
  	for(int i=0;i<n;i++) {
  		for(int j=0;j<m;j++) {
  			A[i][j]=i();
  		}
  	}
  	return A;
  }
  static char[][] charinput(int n,int m){
  	char A[][]=new char[n][m];
  	for(int i=0;i<n;i++) {
  		String s=s();
  		for(int j=0;j<m;j++) {
  			A[i][j]=s.charAt(j);
  		}
  	}
  	return A;
  }
  static int max(int A[]) {
  	int max=Integer.MIN_VALUE;
  	for(int i=0;i<A.length;i++) {
  		max=Math.max(max, A[i]);
  	}
  	return max;
  }
  static int min(int A[]) {
  	int min=Integer.MAX_VALUE;
  	for(int i=0;i<A.length;i++) {
  		min=Math.min(min, A[i]);
  	}
  	return min;
  }
  static long max(long A[]) {
  	long max=Long.MIN_VALUE;
  	for(int i=0;i<A.length;i++) {
  		max=Math.max(max, A[i]);
  	}
  	return max;
  }
  static long min(long A[]) {
  	long min=Long.MAX_VALUE;
  	for(int i=0;i<A.length;i++) {
  		min=Math.min(min, A[i]);
  	}
  	return min;
  }
  static long mod(long x) {
  	 int mod=1000000007;
  	  return ((x%mod + mod)%mod);
  }
  static String reverse(String s) {
  	StringBuffer p=new StringBuffer(s);
  	p.reverse();
  	return p.toString();
  }

       static int i() {
      	 return sc.nextInt();
       }
       static String s() {
      	 return sc.next();
       }
       static long l() {
      	 return sc.nextLong();
       }  
       static void sort(int[] A){
          int n = A.length;
          Random rnd = new Random();
          for(int i=0; i<n; ++i){
              int tmp = A[i];
              int randomPos = i + rnd.nextInt(n-i);
              A[i] = A[randomPos];
              A[randomPos] = tmp;
          }
          Arrays.sort(A);
       }
       static void sort(long[] A){
  	        int n = A.length;
  	        Random rnd = new Random();
  	        for(int i=0; i<n; ++i){
  	            long tmp = A[i];
  	            int randomPos = i + rnd.nextInt(n-i);
  	            A[i] = A[randomPos];
  	            A[randomPos] = tmp;
  	        }
  	        Arrays.sort(A);
  	     }
    static String sort(String s) {
   	 Character ch[]=new Character[s.length()];
   	 for(int i=0;i<s.length();i++) {
   		 ch[i]=s.charAt(i);
   	 }
   	 Arrays.sort(ch);
   	 StringBuffer st=new StringBuffer("");
 for(int i=0;i<s.length();i++) {
	 st.append(ch[i]);
 }
 return st.toString();
}
static HashMap<Integer,Integer> hash(int A[]){
  HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
  for(int i : A) {
	  if(map.containsKey(i)) {
		  map.put(i, map.get(i)+1);
	  }
	  else {
		  map.put(i, 1);
	  }
  }
  return map;
}
static HashMap<Long,Integer> hash(long A[]){
	  HashMap<Long,Integer> map=new HashMap<Long, Integer>();
	  for(long i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
	}
static TreeMap<Integer,Integer> tree(int A[]){
  TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
  for(int i : A) {
	  if(map.containsKey(i)) {
		  map.put(i, map.get(i)+1);
	  }
	  else {
		  map.put(i, 1);
	  }
  }
  return map;
}
static TreeMap<Long,Integer> tree(long A[]){
	  TreeMap<Long,Integer> map=new TreeMap<Long, Integer>();
	  for(long i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
	}
static void primefact(int n) {
	  for(int i=2;i*i<=n;i++) {
		  if(n%i==0) {
			  int cnt=0;
			  while(n%i==0) {
				  cnt++;
				  n/=i;
			  }
			  System.out.println(i+"^"+cnt);
			  
		  }
	  }
	  if(n>1) {
		  System.out.println(n+"^ 1");
	  }
}
   static boolean prime(int n) 
    { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        double sq=Math.sqrt(n);
  
        for (int i = 5; i <= sq; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
   static boolean prime(long n) 
    { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        double sq=Math.sqrt(n);
  
        for (int i = 5; i <= sq; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
   static long power(long x, long y, long p)
   {

       long res = 1;
       x = x % p;

       while (y > 0) {

           if (y % 2 == 1)
               res = (res * x) % p;

           y = y >> 1; 
           x = (x * x) % p;
       }

       return res;
   }

   static long modInverse(long n, long p)
   {
       return power(n, p - 2, p);
   }
   static int gcd(int a, int b) 
   { 
       if (a == 0) 
           return b; 
       return gcd(b % a, a); 
   } 
   static long gcd(long a, long b) 
   { 
       if (a == 0) 
           return b; 
       return gcd(b % a, a); 
   } 
  
      
  static class FastReader 
  { 
      BufferedReader br; 
      StringTokenizer st; 

      public FastReader() 
      { 
          br = new BufferedReader(new
                   InputStreamReader(System.in)); 
      } 

      String next() 
      { 
          while (st == null || !st.hasMoreElements()) 
          { 
              try
              { 
                  st = new StringTokenizer(br.readLine()); 
              } 
              catch (IOException  e) 
              { 
                  e.printStackTrace(); 
              } 
          } 
          return st.nextToken(); 
      } 

      int nextInt() 
      { 
          return Integer.parseInt(next()); 
      } 

      long nextLong() 
      { 
          return Long.parseLong(next()); 
      } 

      double nextDouble() 
      { 
          return Double.parseDouble(next()); 
      } 

      String nextLine() 
      { 
          String str = ""; 
              try
              { 
                  str = br.readLine(); 
              } 
              catch (IOException e) 
              { 
                  e.printStackTrace(); 
              } 
              return str; 
          } 
      } 
  }