You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Alice 有一棵以 $1$ 为根的有根树。

Alice 会与 Bob 玩 $q$ 次游戏。在第 $i$ 次游戏中， Alice 会拥有一个集合 $S_i$ 与一个数 $k_i$。游戏开始时，Alice 会先选出至多 $k_i$ 个集合 $S_i$ 中的元素，并将这些元素在树上代表的节点到根路径上所有边加固。

之后，Bob 会选出树上 $w$ 条没被加固的边割去，使得从根出发不存在通往任意一个叶子节点的路径。假若不存在选边方案，则认为 $w$ 为正无穷。

我们定义在这次游戏中 Alice 与 Bob 的得分分别为 $w$ 和 $-w$。双方都想要最大化自己的得分。假设双方都以最优策略行动，你需要输出每次游戏最后 Alice 的得分是多少。

由于出题人很善良，所以每次游戏给出的集合 $S_i$ 之间差异不会太大。具体而言，我们会给出一个初始集合 $S$，然后对于第 $i$ 次游戏给出两个数 $x,k_i$，代表 $S_i = S \cup x$。

输入格式

本题一个测试点中有多组数据。

第一行一个数 $T$ 表示数据组数。

对于每组数据，第一行三个数 $n,m,q$，在接下来 $n-1$ 行每行两个数 $u,v$ 描述一条树上的边，再接下来一行 $m$ 个数表述初始集合 $S$，再接下来 $q$ 行每行两个数 $x,k_i$ 描述一次游戏。

输出格式

对于每个询问输出一行一个答案。假若答案为正无穷请输出 $-1$。

样例 #1

样例输入 #1

1
5 1 2
1 2
1 3
2 4
2 5
1
1 1
2 1

样例输出 #1

2
3

样例 #2

见附加文件：

exE.in

exE.out

提示

对于所有测试数据，保证满足 $T \leq 5,1 \leq \sum n,\sum q \leq 2.5 \times 10^5,1 \leq m,x,k \leq n$。