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:
//package baobab;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class MOtrees {

    public static void main(String[] args) {
        IO io = new IO();
        int n = io.nextInt(); /* Number of nodes in the tree */
        int queryAmount = io.nextInt();
        Mo mo = new Mo(n, queryAmount);

        /* Read colors of nodes from input. */
        mo.colors = new int[n+1];
        for (int i=1; i<=n; i++) {
            mo.colors[i] = io.nextInt();
        }

        /* Read edges from input, construct tree */
        List<Integer>[] graph = new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i=1; i<n; i++) {
            int a = io.nextInt();
            int b = io.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

        /* Flatten tree into arrays. */
        FlattenedTree f = new FlattenedTree(graph);
        mo.data = f.gen;

        /* These attributes are needed to assign blocks optimally. */
        Query.n = n;
        Query.blocks = (int) (Math.sqrt(n));

        /* Preprocess and sort queries. */
        for (int i=0; i<queryAmount; i++) {
            int root = io.nextInt();
            int size = io.nextInt();
            int a = f.entries[root];
            int b = f.exits[root];
            mo.addQuery(new Query(a, b, size, i));
        }
        mo.sortQueries();

        /* Actual work */
        int[] ans = mo.processQueries();

        /* Print answer */
        for (Integer a : ans) {
            io.println(a);
        }
        io.close();
    }

}

/* The purpose of this is to flatten a tree into arrays for use by MO's algorithm. */
class FlattenedTree {
    int n;
    List<Integer>[] graph;
    int[] entries;
    int[] exits;
    int[] gen; /* Array generated from tree */
    int genPointer;

    /* Generates array with DFS. Graph must hold nodes 1->n. */
    public FlattenedTree(List<Integer>[] graph) {
        this.n = graph.length;
        this.graph = graph;
        entries = new int[n+1];
        exits = new int[n+1];
        gen = new int[n+1];
        genPointer = 1;
        dfs(1);
    }

    private void dfs(int node) {
        if (entries[node] > 0) return;
        gen[genPointer] = node; // entry
        entries[node] = genPointer++;
        for (int neighbor : graph[node]) {
            dfs(neighbor);
        }
        exits[node] = genPointer - 1;
    }

}

class Mo {
    int[] data;
    int n;
    int queryAmount;
    Query[] queries;
    int queryPointer;

    /* Application specific */
    int[] freqOfFreqs = new int[n+1];
    int[] colorFreqs = new int[(int)1e5+1];
    int[] colors;

    /* Application specific */
    public int get(int v) {
        if (v >= freqOfFreqs.length) return 0;
        return freqOfFreqs[v];
    }

    /* Application specific */
    private void add(int i) {
        int node = data[i];
        int color = colors[node];
        colorFreqs[color]++;
        int freq = colorFreqs[color];
        freqOfFreqs[freq]++;
    }

    /* Application specific */
    private void remove(int i) {
        int node = data[i];
        int color = colors[node];
        int freq = colorFreqs[color];
        freqOfFreqs[freq]--;
        colorFreqs[color]--;
    }

    public Mo(int n, int queryAmount) {
        this.n = n;
        this.queryAmount = queryAmount;
        this.queries = new Query[queryAmount];
        this.queryPointer = 0;
    }

    void addQuery(Query q) {
        queries[queryPointer++] = q;
    }

    void sortQueries() {
        Arrays.sort(queries);
    }

    int[] processQueries() {
        int[] ans = new int[queryAmount];
        freqOfFreqs = new int[n+1];

        /* Inclusive indices for sliding query window. */
        int left = 1;
        int right = 0; /* Nodes from 1->n, not 0. */

        for (int i=0; i<queryAmount; i++) {
            Query query = queries[i];
            while (right < query.b) add(++right);
            while (left > query.a) add(--left);
            while (right > query.b) remove(right--);
            while (left < query.a) remove(left++);
            ans[query.idx] = get(query.size);
        }
        return ans;
    }

}

/* Block assigned by a (range left). Sorted by block, ties sorted by b (range right). */
class Query implements Comparable<Query> {
    int a;
    int b;
    int size;
    int block;
    int idx;
    static int blocks;
    static int n;

    public Query(int a, int b, int size, int idx) {
        this.a = a;
        this.b = b;
        this.size = size;
        this.idx = idx;
        this.block = (int) ((1.0 * a / n) * blocks);
    }

    @Override
    public int compareTo(Query o) {
        if (this.block != o.block) {
            return this.block - o.block;
        }
        return this.b - o.b;
    }

}

class IO extends PrintWriter {
    private InputStreamReader r;
    private static final int BUFSIZE = 1 << 15;
    private char[] buf;
    private int bufc;
    private int bufi;
    private StringBuilder sb;

    public IO() {
        super(new BufferedOutputStream(System.out));
        r = new InputStreamReader(System.in);

        buf = new char[BUFSIZE];
        bufc = 0;
        bufi = 0;
        sb = new StringBuilder();
    }

    private void fillBuf() throws IOException {
        bufi = 0;
        bufc = 0;
        while(bufc == 0) {
            bufc = r.read(buf, 0, BUFSIZE);
            if(bufc == -1) {
                bufc = 0;
                return;
            }
        }
    }

    private boolean pumpBuf() throws IOException {
        if(bufi == bufc) {
            fillBuf();
        }
        return bufc != 0;
    }

    private boolean isDelimiter(char c) {
        return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f';
    }

    private void eatDelimiters() throws IOException {
        while(true) {
            if(bufi == bufc) {
                fillBuf();
                if(bufc == 0) throw new RuntimeException("IO: Out of input.");
            }

            if(!isDelimiter(buf[bufi])) break;
            ++bufi;
        }
    }

    public String next() {
        try {
            sb.setLength(0);

            eatDelimiters();
            int start = bufi;

            while(true) {
                if(bufi == bufc) {
                    sb.append(buf, start, bufi - start);
                    fillBuf();
                    start = 0;
                    if(bufc == 0) break;
                }

                if(isDelimiter(buf[bufi])) break;
                ++bufi;
            }

            sb.append(buf, start, bufi - start);

            return sb.toString();
        } catch(IOException e) {
            throw new RuntimeException("IO.next: Caught IOException.");
        }
    }

    public int nextInt() {
        try {
            int ret = 0;

            eatDelimiters();

            boolean positive = true;
            if(buf[bufi] == '-') {
                ++bufi;
                if(!pumpBuf()) throw new RuntimeException("IO.nextInt: Invalid int.");
                positive = false;
            }

            boolean first = true;
            while(true) {
                if(!pumpBuf()) break;
                if(isDelimiter(buf[bufi])) {
                    if(first) throw new RuntimeException("IO.nextInt: Invalid int.");
                    break;
                }
                first = false;

                if(buf[bufi] >= '0' && buf[bufi] <= '9') {
                    if(ret < -214748364) throw new RuntimeException("IO.nextInt: Invalid int.");
                    ret *= 10;
                    ret -= (int)(buf[bufi] - '0');
                    if(ret > 0) throw new RuntimeException("IO.nextInt: Invalid int.");
                } else {
                    throw new RuntimeException("IO.nextInt: Invalid int.");
                }

                ++bufi;
            }

            if(positive) {
                if(ret == -2147483648) throw new RuntimeException("IO.nextInt: Invalid int.");
                ret = -ret;
            }

            return ret;
        } catch(IOException e) {
            throw new RuntimeException("IO.nextInt: Caught IOException.");
        }
    }

    public long nextLong() {
        try {
            long ret = 0;

            eatDelimiters();

            boolean positive = true;
            if(buf[bufi] == '-') {
                ++bufi;
                if(!pumpBuf()) throw new RuntimeException("IO.nextLong: Invalid long.");
                positive = false;
            }

            boolean first = true;
            while(true) {
                if(!pumpBuf()) break;
                if(isDelimiter(buf[bufi])) {
                    if(first) throw new RuntimeException("IO.nextLong: Invalid long.");
                    break;
                }
                first = false;

                if(buf[bufi] >= '0' && buf[bufi] <= '9') {
                    if(ret < -922337203685477580L) throw new RuntimeException("IO.nextLong: Invalid long.");
                    ret *= 10;
                    ret -= (long)(buf[bufi] - '0');
                    if(ret > 0) throw new RuntimeException("IO.nextLong: Invalid long.");
                } else {
                    throw new RuntimeException("IO.nextLong: Invalid long.");
                }

                ++bufi;
            }

            if(positive) {
                if(ret == -9223372036854775808L) throw new RuntimeException("IO.nextLong: Invalid long.");
                ret = -ret;
            }

            return ret;
        } catch(IOException e) {
            throw new RuntimeException("IO.nextLong: Caught IOException.");
        }
    }

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

}