F. Цветное дерево Хуана
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У Хуана есть красивое дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Также есть $$$k$$$ различных цветов, пронумерованных от $$$1$$$ до $$$k$$$. Каждая вершина $$$u$$$ в дереве имеет свой собственный набор $$$C_u$$$, который содержит цвета. Обозначим за $$$s$$$ сумму $$$\sum_{i=1}^n \left| C_i \right|$$$.

Есть $$$q$$$ запросов, в которых вам будут даны вершины $$$u$$$ и $$$v$$$. Обозначим $$$P$$$ как множество всех вершин на простом пути между $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите на одной строке ответы на все запросы в порядке их появления во входных данных, разделённые пробелами.

Пример
Входные данные
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
Выходные данные
2 2 3 5 
1 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)$$$ соответствуют следующим значениям:

  • $$$\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$$$