Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance.
×

Codeforces Round 221 (Div. 1) |
---|

Finished |

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.

data structures

dfs and similar

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2024 06:50:22 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|