I. Magical Zoo
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Thomas owns a zoo filled with red pandas. The zoo can be described as a graph with $$$n$$$ nodes numbered $$$1 \dots n$$$ and $$$n-1$$$ bidirectional paths such that all pairs of nodes are connected through some series of paths.

Each node in this graph is either a feeding station or an exhibit. There are $$$k$$$ exhibits, and $$$n-k$$$ feeding stations. All nodes $$$i$$$ such that $$$1 \leq i \leq k$$$ are exhibits, while the rest of the nodes are feeding stations.

A feeding station at node $$$j$$$ ($$$k+1 \leq j \leq n$$$) contains cereal of color $$$c_j$$$, and when a red panda eats at this feeding station, its fur color becomes color $$$c_j$$$.

There are $$$m$$$ red pandas in this zoo, initially colored with color $$$0$$$ (which is red!). Red panda $$$p$$$ ($$$1 \leq p \leq m$$$) travels from node $$$a_p$$$ to node $$$b_p$$$ through the shortest series of paths, stopping at all feeding stations on the way to eat (including at $$$a_p$$$ and $$$b_p$$$).

For each of the $$$k$$$ exhibits, how many uniquely colored red pandas have been there? (including red pandas that start or end at the exhibit)

Input

The first line contains two space separated integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 3 \cdot 10^5$$$).

The next line contains $$$n-k$$$ space separated integers. The $$$i$$$th integer represents color $$$c_{i+k}$$$, the color of the cereal of the feeding station at node $$$i + k$$$. ($$$1 \leq c_{i + k} \leq n$$$)

The next $$$n - 1$$$ lines contain two space separated integers $$$u_i$$$ and $$$v_i$$$, representing a path between nodes $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$). It is guaranteed that these paths form a tree.

The next line contains one integer $$$m$$$, representing the number of red pandas. ($$$1 \leq m \leq 3 \cdot 10^5$$$)

The next $$$m$$$ lines contains two space separated integers $$$a_j$$$ and $$$b_j$$$, the path of the $$$j$$$th red panda ($$$1 \leq a_j, b_j \leq n$$$).

Output

Output $$$k$$$ lines, with the $$$i$$$th line containing one integer describing the number of uniquely colored red pandas that have crossed the exhibit at node $$$i$$$.

Example
Input
2 1
1
1 2
3
2 1
1 1
1 2
Output
2
Note

Two uniquely colored red pandas have been at node $$$1$$$. Red pandas $$$2$$$ and $$$3$$$ were color $$$0$$$ at node $$$1$$$, and red panda $$$1$$$ was color $$$1$$$ at node $$$1$$$.

Problem Credits: Eric Hsu