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.io.*;
import java.math.*;
import java.security.KeyStore.Entry;
import java.util.*;

public class TestClass {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;

	static int st[], et[],df[], time = 0;
	static boolean u[];
	static ArrayList<Integer> a[];

	public static void dfs(int n) {
		u[n] = true;
		df[time] = n;
		st[n] = time++;
		for (int i = 0; i < a[n].size(); i++) {
			if (!u[a[n].get(i)])
				dfs(a[n].get(i));
		}
		et[n] = time - 1;
	}

	public static class Query implements Comparable<Query> {
		int l, r, in, bn, k;

		Query(int a, int b, int c, int d, int e) {
			l = a;
			r = b;
			in = c;
			bn = d;
			k = e;
		}

		public int compareTo(Query o) {
			return bn != o.bn ? Integer.compare(bn, o.bn) : Integer.compare(r, o.r);
		}
	}

	private static void soln() {
		int n = nI(), query = nI();
		int color[] = new int[n];
		st = new int[n];
		et = new int[n];
		df = new int[n];
		u = new boolean[n];
		for (int i = 0; i < n; i++)
			color[i] = nI();
		a = new ArrayList[n];
		for (int i = 0; i < n; i++)
			a[i] = new ArrayList<Integer>();
		for (int i = 0; i < n - 1; i++) {
			int x = nI() - 1;
			int y = nI() - 1;
			a[x].add(y);
			a[y].add(x);
		}
		dfs(0);
		Query q[] = new Query[query];
		int sr = (int) Math.sqrt(n);
		for (int i = 0; i < query; i++) {
			int nm = nI() - 1, k = nI();
			q[i] = new Query(st[nm], et[nm], i, st[nm] / sr, k);
		}
		int cnt[] = new int[100001];
		int cnt1[] = new int[100001];
		Arrays.sort(q);
		int l = 0, r = -1;
		int ans[] = new int[query];
		for (int i = 0; i < query; i++) {
			while (r < q[i].r) {
				cnt[color[df[++r]]]++;
				cnt1[cnt[color[df[r]]]]++;
			}
			while (l > q[i].l) {
				cnt[color[df[--l]]]++;
				cnt1[cnt[color[df[l]]]]++;
			}
			while (l < q[i].l) {
				cnt1[cnt[color[df[l]]]]--;
				cnt[color[df[l++]]]--;
			}
			while (r > q[i].r) {
				cnt1[cnt[color[df[r]]]]--;
				cnt[color[df[r--]]]--;
			}
			ans[q[i].in] = cnt1[q[i].k];
		}
		for (int i = 0; i < query; i++)
			pw.println(ans[i]);
	}

	public static void main(String[] args) {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		soln();
		pw.close();
	}

	// To Get Input
	// Some Buffer Methods
	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}

	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nI() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nL() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nLi() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}