题目描述

Meta 内部网球锦标赛 Whacker Cup 将在公司园区内的 $N$ 个网球场举行，网球场编号为 $1..N$。其中 $1$ 号场地是 Whacker Square，开幕式将在这里举行。

开幕式结束后，参赛者会通过园区内的 $M$ 条电车线路前往其他网球场，线路编号为 $1..M$。第 $i$ 条线路会依次经过 $L_i \ge 2$ 个互不相同的网球场：

$$A_{i,1}\to A_{i,2}\to \cdots \to A_{i,L_i}.$$

一次乘坐电车时，乘客可以在某条经过其当前位置的线路上车，最多乘坐 $K$ 站后下车。

例如，当 $K=2$，某条线路为 $1\to 5\to 7\to 2$ 时，一次乘车中：

• 乘客可以从 $1$ 号场上车，在 $5$ 号或 $7$ 号场下车；
• 可以从 $5$ 号场上车，在 $7$ 号或 $2$ 号场下车；
• 可以从 $7$ 号场上车，在 $2$ 号场下车。

作为 CTO（Chief Transportation Officer），你希望确保园区交通足够便利。对于一个目的地 $x$，设 $D(x)$ 表示从 $1$ 号场到 $x$ 号场所需的最少电车乘坐次数；若无法到达，则 $D(x)=-1$。

请计算：

$$\sum_{i=1}^{N} D(i)\times i.$$

数据范围

• $1 \le T \le 90$
• $2 \le N \le 500{,}000$
• $1 \le K < N$
• $1 \le M \le 500{,}000$
• $2 \le L_i \le N$
• $1 \le A_{i,j} \le N$
• 每条线路中的站点互不相同。
• 所有线路的 $L_i$ 之和不超过 $1{,}000{,}000$。

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

每个测试用例中：

第一行包含三个空格分隔的整数 $N,K,M$。

接下来 $M$ 行，第 $i$ 行先包含一个整数 $L_i$，随后包含 $L_i$ 个整数 $A_{i,1},\ldots,A_{i,L_i}$。

输出格式

对于第 $i$ 个测试用例，输出：

Case #i: x

其中 $x$ 为所有目的地 $i=1..N$ 的 $D(i)\times i$ 之和。

样例输入

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

样例输出

Case #1: 31
Case #2: 22
Case #3: 40
Case #4: 14
Case #5: -10

样例解释

第一个样例中，有 $N=7$ 个网球场，每次最多乘坐 $K=2$ 站，有 $M=2$ 条线路：

$$1\to 5\to 7\to 2$$

以及

$$2\to 3\to 4.$$

各个 $D$ 值如下：

• 从 $1$ 号场到自身不需要乘车，所以 $D(1)=0$；
• 从 $1$ 号场到 $2$ 号场至少需要 $D(2)=2$ 次乘车。由于一次最多乘坐 $K=2$ 站，需要先下车再重新上车；
• 从 $1$ 号场到 $3$ 号场至少需要 $D(3)=3$ 次乘车。例如可以先坐 $1\to 5\to 7$，再坐 $7\to 2$，最后坐 $2\to 3$；
• 从 $1$ 号场到 $4$ 号场至少需要 $D(4)=3$ 次乘车。例如可以先坐 $1\to 5\to 7$，再坐 $7\to 2$，最后坐 $2\to 3\to 4$；
• 同理，$D(5)=1$，$D(6)=-1$，$D(7)=1$。

最终答案为：

$$1\times 0+2\times 2+3\times 3+4\times 3+5\times 1+6\times (-1)+7\times 1=31.$$

第二个样例中，有 $N=5$ 个网球场，每次最多乘坐 $K=1$ 站，有 $M=2$ 条线路。各场地最少乘车次数为：

$$D=[0,1,2,1,2],$$

因此答案为：

$$1\times 0+2\times 1+3\times 2+4\times 1+5\times 2=22.$$