Juan有一棵美丽的树,其中有$$$n$$$节点,编号从$$$1$$$到$$$n$$$。还有 $$$k$$$ 不同的颜色,编号从 $$$1$$$ 到 $$$k$$$。树中的每个节点 $$$u$$$ 都有自己的包含颜色的集合 $$$C_u$$$。让我们用 $$$s$$$ 表示数量 $$$\sum_{i=1}^n \left| C_i \right|$$$。
有 $$$q$$$ 查询,您将获得节点 $$$u$$$ 和 $$$v$$$。让 $$$P$$$ 表示 $$$u$$$ 和 $$$v$$$ 之间的简单路径中的所有节点的集合,包括 $$$u$$$ 和 $$$v$$$。您需要为每个查询计算以下数量:$$\left| \bigcap_{w \in P} C_w \right|$$
即从$$$u$$$到$$$v$$$路径中所有节点的集合的交集的基数。换句话说,计算从 $$$u$$$ 到 $$$v$$$ 的路径上每组中出现了多少种颜色。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含四个整数 $$$n$$$、$$$k$$$、$$$s$$$ 和 $$$q$$$ ($$$1 \le n, k, q \le 3 \cdot 10^5, 1 \le s \le \min (nk, 3 \cdot 10^5)$$$) — 树中的节点数,分别是不同颜色的数量、所有颜色集的基数之和以及查询数量。
接下来的 $$$n-1$$$ 行每行包含两个整数 $$$u$$$、$$$v$$$ ($$$1 \le u, v \le n$$$),表示节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。
接下来的 $$$s$$$ 行每行包含两个整数 $$$v$$$ 和 $$$x$$$ ($$$1 \le v \le n, 1 \le x \le k$$$) 表示颜色 $$$x$$$ 位于 $$$C_v$$$ 中。所有 $$$s$$$ 行都是成对不同的。
接下来的 $$$q$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示节点 $$$u$$$ 和 $$$v$$$ 之间的查询。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
保证所有测试用例的 $$$k$$$ 总和不超过 $$$3 \cdot 10^5$$$。
保证所有测试用例的 $$$s$$$ 总和不超过 $$$3 \cdot 10^5$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行:所有查询的答案按照它们在输入中出现的顺序排列,用空格分隔。
示例
输入复制
23 5 10 41 32 11 11 21 31 41 52 12 22 53 13 21 32 31 21 19 3 12 107 22 46 89 62 15 82 53 91 36 19 39 15 12 38 14 35 38 37 33 14 71 44 55 54 29 92 22 25 27 3
输出复制
2 2 3 51 1 1 2 1 2 1 1 1 0
注意
在第一个测试用例中,有一个由 $$$3$$$ 节点组成的树,其边为 $$$(1, 3)$$$ 和 $$$(2, 1)$$$。每个节点集合中的颜色为:
- $$$C_1 = \{ 1, 2, 3, 4, 5 \}$$$
- $$$C_2 = \{ 1, 2, 5 \}$$$
- $$$C_3 = \{ 1, 2 \}$$$
$$$4$$$ 查询位于节点对 $$$(1, 3)$$$、$$$(2, 3)$$$、$$$(1, 2)$$$、$$$(1, 1)$$$ 之间,分别对应于计算以下数量:
- $$$\左| C_1 \cap C_3 \right| = \左| \{ 1, 2 \} \right| = 2$$$
- $$$\左| C_2 \cap C_1 \cap C_3 \right| = \左| \{ 1, 2 \} \right| = 2$$$
- $$$\左| C_2 \cap C_1 \right| = \左| \{ 1, 2, 5 \} \right| = 3$$$
- $$$\左| C_1 \右| = \左| \{ 1, 2, 3, 4, 5 \} \right| = 5$$$