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-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2017 22:28:56 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|