题目描述

Juku 有一棵包含 $N$ 个顶点的二叉树，这棵树不一定平衡。树的顶点编号为 $1 \ldots N$，根节点为 $1$。

每个叶子节点中都写有一个数。对于其他节点，Juku 可以任选放置一个 MIN 元素或 MAX 元素：

• MIN 元素会把该节点的值设为其子节点值中的较小者；
• MAX 元素会把该节点的值设为其子节点值中的较大者。

Juku 想对若干个不同的数进行询问：为了使根节点的值大于或等于给定的数，最少需要在树中放置多少个 MAX 元素？

请编写程序回答这些询问。

输入格式

第一行包含一个整数 $N$，表示树的顶点数。

接下来 $N-1$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示顶点 $A_i$ 和 $B_i$ 之间有一条边。

随后若干行描述叶子节点的值。每行包含两个整数 $X_j$ 和 $Y_j$，其中 $X_j$ 是一个叶子节点的编号，$Y_j$ 是写在该叶子节点中的值。

这样的行数等于树中叶子节点的数量。

接下来一行包含一个整数 $Q$，表示 Juku 的询问数量。

接下来 $Q$ 行，每行包含一个整数 $M_k$，表示 Juku 想询问的目标值。

输出格式

对于每个询问输出一行答案。

如果可以使根节点得到一个大于或等于 $M_k$ 的值，则输出所需 MAX 元素数量的最小值。

如果无法得到这么大的根节点值，则输出 $-1$。

答案按询问在输入中出现的顺序输出。

数据范围

$3 \le N \le 10^5$

$1 \le A_i,B_i \le N$

$A_i \ne B_i$

$1 \le X_j \le N$

$0 \le Y_j \le 10^7$

$1 \le Q \le 5 \cdot 10^5$

$0 \le M_k \le 10^7$

样例

输入

5
1 2
2 3
5 1
4 2
3 7
4 5
5 12
3
10
4
23

输出

1
0
-1

样例说明

第一次询问中，Juku 想知道至少需要多少个 MAX 元素才能使根节点得到数值 $10$。唯一足够大的数在编号为 $5$ 的叶子中，为了让这个数传到根节点，需要在顶点 $1$ 放置 MAX 元素。

第二次询问目标值为 $4$。因为所有叶子中的值都大于该目标值，所以不需要任何 MAX 元素。

第三次询问目标值为 $23$。它大于所有叶子中的数，因此不可能使根节点得到这么大的值。

评分方式

本题测试点分组计分。只有通过一个组内所有测试，才能获得该组分数。

各组附加限制如下：

1. 20 分：$N \le 20$，$Q \le 10$，且所有 $M_k \le 100$；
2. 20 分：$N \le 1000$，$Q \le 1000$；
3. 20 分：树中除了第一层外，每一层恰好有 2 个顶点；
4. 20 分：$Q \le 100$，所有 $Y_j \le 100$，所有 $M_k \le 100$；
5. 20 分：无额外限制。