题目描述

一片区域中有 $n$ 座城市，城市之间由若干条双向道路相连。现在需要选择其中一座城市建设应急指挥中心。

指挥中心确定后，除指挥中心所在城市外，还会有一座城市随机进入临时封锁状态。每一座其余城市被选中的概率均为 $\frac{1}{n-1}$。处于封锁状态的城市不能被任何信息传输路径经过。

现有 $q$ 种应急事件方案。第 $i$ 种方案中共有 $k_i$ 份应急报告，每份报告存放在指定的一座城市中；同一座城市中可能存放多份报告。若某份报告所在城市到指挥中心之间存在一条不经过封锁城市的路径，则该报告能够成功送达指挥中心。

对于每一种应急事件方案，你都可以重新选择指挥中心所在城市。请最大化能够成功送达指挥中心的报告数量的期望值，并输出该最大期望值乘以 $n-1$ 的结果。可以证明，输出值一定是整数。

输入格式

输入的第一行有三个整数 $n,m,q$，分别表示城市数量、道路数量和应急事件方案数量。

接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示城市 $x_i$ 和城市 $y_i$ 之间有一条双向道路。保证没有重边和自环。

接下来 $q$ 行，每行描述一种应急事件方案。每行的第一个整数 $k_i$ 表示报告数量，接下来的 $k_i$ 个整数表示每份报告所在的城市。注意，多份报告可能位于同一座城市。

输出格式

输出共 $q$ 行。对于每一种方案，输出能够成功送达指挥中心的报告数量的最大期望值乘以 $n-1$ 的结果。

样例

样例输入 1

4 4 2
1 2
1 3
2 3
1 4
2 2 4
2 1 4

样例输出 1

4
5

数据范围与提示

$subtask 1(20pts)$：$n \leq 100,m \leq 200,q \leq 100$。

$subtask 2(20pts)$：$n \leq 2000,m \leq 10000,\sum k_i \leq 5000$。

$subtask 3(20pts)$：保证图是一棵树。

$subtask 4(40pts)$：无特殊限制。

对于所有数据，满足 $1 \leq n \leq 2 \times 10^5,1 \leq m \leq 5 \times 10^5,1 \leq q \leq 5 \times 10^5,\sum k_i \leq 5 \times 10^5$，保证图连通。