Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Tree and Queries

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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* _{ v}. 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* _{ j}, *k* _{ j}. The answer to query *v* _{ j}, *k* _{ j} is the number of such colors of vertices *x*, that the subtree of vertex *v* _{ j} contains at least *k* _{ j} 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* ≤ 10^{5}; 1 ≤ *m* ≤ 10^{5}). The next line contains a sequence of integers *c* _{1}, *c* _{2}, ..., *c* _{ n} (1 ≤ *c* _{ i} ≤ 10^{5}). The next *n* - 1 lines contain the edges of the tree. The *i*-th line contains the numbers *a* _{ i}, *b* _{ i} (1 ≤ *a* _{ i}, *b* _{ i} ≤ *n*; *a* _{ i} ≠ *b* _{ i}) — the vertices connected by an edge of the tree.

Next *m* lines contain the queries. The *j*-th line contains two integers *v* _{ j}, *k* _{ j} (1 ≤ *v* _{ j} ≤ *n*; 1 ≤ *k* _{ j} ≤ 10^{5}).

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*.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/07/2020 13:28:26 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|