题目描述

你有一棵 $n$ 个点的无根树，节点编号从 $1$ 开始，和一个初始为空的可重集合 $S$。有 $m$ 次向 $S$ 中加入元素的操作，第 $i$ 次操作给出原树中的 $k_i$ 条边，保证互不相同，你需要将这 $k_i$ 条边删去，得到 $k_i + 1$ 个联通块，设构成这些联通块的点的编号集合分别为 $T_{i,1}, T_{i,2}, \dots, T_{i,k_i+1}$，你需要将这些集合加入 $S$，注意每次操作是互相独立的。

在所有 $m$ 次加入操作后，有 $q$ 次询问，第 $i$ 次询问给定树上一个点 $u_i$ 和一个半径 $r_i$，对于所有原树上到 $u_i$ 简单路径边数小于等于 $r_i$ 的点的编号构成的集合 $C_i$，你需要求出 $S$ 中有多少个元素是 $C_i$ 的子集。

输入格式

第一行四个正整数 $subid, n, m, q$，其中 $subid$ 表示其符合 Subtask #id 的特殊性质，其余同题目描述。

接下来 $n-1$ 行中，第 $i$ 行两个正整数 $a_i, b_i$ 表示树上编号为 $i$ 的边的两个端点。

接下来 $m$ 行中，第 $i$ 行先输入一个正整数 $k_i$，紧接着输入 $k_i$ 个正整数表示这次操作删去的边的编号集合，保证合法且互不相同。

接下来 $q$ 行中，第 $i$ 行两个整数 $u_i, r_i$ 表示给定点的标号和半径。

输出格式

共输出 $q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

样例输入 1

1 7 1 3
1 3
1 2
1 4
7 2
5 4
2 6
2 4 5
4 3
7 3
2 1

样例输出 1

3
2
1

样例输入 2

1 15 3 5
12 7
5 13
1 5
1 6
15 1
4 11
1 3
4 8
1 2
1 7
3 4
13 14
10 6
9 4
2 1 10
2 6 12
2 3 12
4 2
1 0
15 3
8 5
6 5

样例输出 2

1
0
3
6
9

数据范围

对于所有测试点，都满足 $1 \le n \le 10^5, 1 \le m+\sum k, q \le 3 \times 10^5$，$\forall i, 0 \le r_i \le n$。