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>).
from collections import defaultdict

def dfs(v, parent, colors, subtree_counts):
    # Initialize a dictionary to store color counts in the subtree rooted at v.
    color_count = defaultdict(int)
    
    # Count the color of the current vertex.
    color_count[colors[v - 1]] = 1
    
    # Traverse all child vertices.
    for u in tree[v]:
        if u != parent:
            # Perform DFS on the child and get its color count.
            child_color_count = dfs(u, v, colors, subtree_counts)
            
            # Merge the child's color count into the current vertex's color count.
            for color, count in child_color_count.items():
                color_count[color] += count
    
    # Update the global subtree_counts dictionary with color counts for vertex v.
    subtree_counts[v] = color_count
    
    return color_count

# Read input
n, m = map(int, input().split())
colors = list(map(int, input().split()))

# Initialize the tree as an adjacency list.
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# Initialize a dictionary to store color counts in the subtree for each vertex.
subtree_counts = {}

# Perform DFS starting from the root (vertex 1) to compute color counts in subtrees.
dfs(1, 0, colors, subtree_counts)

# Process queries and print answers
for _ in range(m):
    vj, kj = map(int, input().split())
    colors_count = subtree_counts[vj]
    ans = sum(1 for count in colors_count.values() if count >= kj)
    print(ans)
