F. Juan's Colorful Treetime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output Juan has a beautiful tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. There are also $$$k$$$ distinct colors numbered from $$$1$$$ to $$$k$$$. Each node $$$u$$$ in the tree has its own set $$$C_u$$$ which contains colors. Let's denote with $$$s$$$ the quantity $$$\sum_{i=1}^n \left| C_i \right|$$$.There are $$$q$$$ queries where you will be given nodes $$$u$$$ and $$$v$$$. Let $$$P$$$ denote the set of all nodes in the simple path between $$$u$$$ and $$$v$$$, inclusive. You are asked to calculate for each query the following quantity: $$$$$$\left| \bigcap_{w \in P} C_w \right|$$$$$$That is, the cardinality of the intersection of the sets of all the nodes in the path from $$$u$$$ to $$$v$$$. In other words, calculate how many colors appear in every set on the path from $$$u$$$ to $$$v$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$s$$$, and $$$q$$$ ($$$1 \le n, k, q \le 3 \cdot 10^5, 1 \le s \le \min (nk, 3 \cdot 10^5)$$$) — the number of nodes in the tree, the number of distinct colors, the sum of the cardinalities of all sets of colors, and the number of queries, respectively.The next $$$n-1$$$ lines each contain two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$), indicating that there's an edge between nodes $$$u$$$ and $$$v$$$.The next $$$s$$$ lines each contain two integers $$$v$$$ and $$$x$$$ ($$$1 \le v \le n, 1 \le x \le k$$$) indicating that color $$$x$$$ is in $$$C_v$$$. All $$$s$$$ lines are pairwise distinct.The next $$$q$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), indicating a query between nodes $$$u$$$ and $$$v$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$. It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$. It is guaranteed that the sum of $$$s$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$. It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$. OutputFor each test case, output a line: the answer to all queries in the order they appear in the input, separated by spaces.ExampleInput23 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 3Output2 2 3 5 1 1 1 2 1 2 1 1 1 0 NoteIn the first test case, there is a tree of $$$3$$$ nodes with edges $$$(1, 3)$$$ and $$$(2, 1)$$$. The colors in the sets of each node are: $$$C_1 = \{ 1, 2, 3, 4, 5 \}$$$ $$$C_2 = \{ 1, 2, 5 \}$$$ $$$C_3 = \{ 1, 2 \}$$$ The $$$4$$$ queries are between the pairs of nodes $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(1, 2)$$$, $$$(1, 1)$$$ and correspond to calculating the following quantities respectively: $$$\left| C_1 \cap C_3 \right| = \left| \{ 1, 2 \} \right| = 2$$$ $$$\left| C_2 \cap C_1 \cap C_3 \right| = \left| \{ 1, 2 \} \right| = 2$$$ $$$\left| C_2 \cap C_1 \right| = \left| \{ 1, 2, 5 \} \right| = 3$$$ $$$\left| C_1 \right| = \left| \{ 1, 2, 3, 4, 5 \} \right| = 5$$$