Yoshinow2001 has not logged in the GenshinImpact for a long time, and there are many more Dendroculus on the map of the Teyvat continent.
The map of the GenshinImpact can be seen as an undirected connected graphundirected connected graph G=(V,E) of n points, m edges, where each vertex v∈V represents a location on the map, and each edge e=(vs,vt) represents a road from the point vs to vt.
Since Yoshinow2001 has a lot of Dendroculus did not take, so he will give you a total of Q queries, each query indicates that there are k vertexs a1,a2,…,ak on the graph G, these vertexs need to take Dendroculus. He wants to know how many vertex pairs (S,T) satisfy 1≤S≤T≤n so that any simple path from S to T passes through all vertexs in the set a1,…,ak exactly once.
Each test contains multiple test cases.The first line of input contains a single integer T(1≤T≤1×10^4)----the number of test cases.The desc
The first line contains three integers n,m,Q(1≤n≤5×10^5,1≤m,Q≤1×10^6) correspondingly represent the number of vertexs, the number of edges, the number of queries.
The following m lines contains two integers ui,vi(ui=vi) indicating an undirected edge between ui and vi. It is guaranteed that ∀i,j:1≤i<j≤m satisfy (ui,vi)=(uj,vj).
The following Q lines. Each line begins with an integer k, representing the number of vertexs queried. Next k integers a1,…,ak, representing the vertexs.
It is guaranteed that the sum of n for each test cases does not exceed 1.5×1061.5×106, the sum of m, Q, ∑i=1Qki for each test cases does not exceed 3×10^6.
For each test case, output Q lines, where the i-th line contains an integer, representing the answer to the i-th query.
Notes: In this problem, you may need more stack space to pass this problem. We suggest you to add the following code into your main function if you use C++
int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
...
exit(0);
}
And if you use the code above please DON’T forget to add exit(0)DON’T forget to add exit(0); in the end of your main function, otherwise your code may get RE
1
3 3 3
1 3
3 2
1 2
1 1
2 2 3
3 1 2 33
1
0