F. Juan's Colorful Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard 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$$$.

Input

Each 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$$$.

Output

For each test case, output a line: the answer to all queries in the order they appear in the input, separated by spaces.

Example
Input
2
3 5 10 4
1 3
2 1
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 5
3 1
3 2
1 3
2 3
1 2
1 1
9 3 12 10
7 2
2 4
6 8
9 6
2 1
5 8
2 5
3 9
1 3
6 1
9 3
9 1
5 1
2 3
8 1
4 3
5 3
8 3
7 3
3 1
4 7
1 4
4 5
5 5
4 2
9 9
2 2
2 2
5 2
7 3
Output
2 2 3 5 
1 1 1 2 1 2 1 1 1 0
Note

In 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$$$