给定一棵 n 个点的树,树上的节点依次编号为 1 到 n。这一颗树的根节点为 1。
给定一个长度为 m 的正整数序列 a1,⋯,am,满足 ∀i,ai∈[1,n]。
q 次询问,每次询问给出 2k 个数 l1,r1,⋯,lk,rk,满足 ∀i,1≤li≤ri≤m。
我们不妨记数组 a 中由这 k 个子区间拼接而成的序列 al1,al1+1,⋯,ar1,al2,al2+1,⋯,ar2,⋯,alk,alk+1,⋯,ark 为 b1,⋯,bs,你需要求出有几个 i 满足如下条件:
- 1≤i≤s。
- ∀1≤j≤i,bi=bj 或者 bi 为 bj 的祖先节点。
输入格式
第一行三个正整数 n、m、q。
接下来 n−1 行,每行两个正整数 xi、yi,表示一条连接 xi,yi 的树边。
接下来一行有 m 个数,依次表示 a1,⋯,am。
接下来 q 行,每行第一个正整数表示 k,之后 2k 个正整数,依次表示 l1,r1,l2,r2,⋯,lk,rk。
输出格式
q 行,每行一个数表示这一次询问答案。
样例数据
样例输入
5 10 3
1 2
1 3
2 4
2 5
3 5 1 2 5 2 5 1 4 1
1 1 10
2 4 5 6 7
1 4 7
样例输出
4
2
2
子任务
由于本题数据规模可以达到 27MB,请注意自己的 IO 用时。
Subtask 1(10%):给定的树是一条链。
Subtask 2(20%):k=1。
Subtask 3(30%):n,m,∑k≤100000。
Subtask 4(40%):无特殊限制。
对于所有测试数据,满足 n,m,∑k≤700000。