题目背景

一座城市的地铁客流量是非常重要的指标，它体现了这座城市正在不断流动着的人口数量。无论通勤还是旅游，都会给这座城市的经济带来活力。

疫情期间各地地铁客流惨淡，甚至有部分城市地铁停运。现在疫情态势好转，各地陆续复工复产，地铁客流量大小也是判断城市复工复产、经济恢复率的重要参考。

题目描述

天穹市的地铁系统由 $M$ 条线路组成，共有 $N$ 座车站，每座车站都会有线路停靠。每条线路的相邻两站之间可视为由无向边连接。其中地铁 $i$ 号线上有 $k_i$ 座车站，这些车站互不相同。

这些线路会在一些车站相交，也就是说，一座车站可能有很多线路停靠。

现在，有 $P$ 位乘客分别想从 $s_j$ 号车站出发，去 $t_j$ 号车站，保证这两座车站不同。当这两座车站不在一条线路上时，他就会进行若干次换乘。作为天穹地铁的技术工作人员，你需要计算这些乘客贡献的客流量。

---

请注意，在这里使用的客流量计算方法和实际应用中的有所不同。

客流量 $=$ 进站客流 $+$ 换乘客流。进站客流即为乘客数；换乘客流为乘客的换乘次数。起终点之间可能会有多条路径可以选择，此时，地铁客流量与 乘客选择的 路径无关；计算时，我们只考虑 换乘次数最少 的路径。

---

注意：

• 设从 $s$ 到 $t$ 最少进行 $\rm trans$ 次换乘，则此时要乘坐 $\rm trans + 1$ 条线路，贡献 $\rm trans + 1$ 的客流量。
• 当乘客不能从起点到达终点时，即 $s, t$ 之间没有通路，他就会去坐公交，此时客流量计为 $0$。

输入格式

第一行三个整数 $N, M, P$。

接下来 $M$ 行，每行表示一条地铁线路：
每行第一个整数为 $k_i\ (2 \le k_i \le N)$，为这条线的车站数；
后面 $k_i$ 个整数 $q\ (1 \le q \le N)$，为这条线路依次经过的车站编号。

接下来 $P$ 行，每行两个整数 $s_j, t_j\ (1 \le s_j, t_j \le N;\ s_j \neq t_j)$，表示一位乘客的出行起终点。

输出格式

仅一行一个整数，表示这些乘客贡献的客流量。

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

9

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

7

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

3

提示

样例解释：

• 默认乘客会选择换乘次数最少的路径。
• 边上的数字表示所在地铁线路的编号。

样例 1 如图：

乘客 $1$ 会乘坐 $1$ 号线从 $1$ 到 $3$，再乘坐 $2$ 号线从 $3$ 到 $6$；
乘客 $2$ 会乘坐 $3$ 号线从 $4$ 到 $2$，再乘坐 $1$ 号线从 $2$ 到 $3$；
乘客 $3$ 会乘坐 $4$ 号线从 $4$ 到 $8$；
乘客 $4$ 会乘坐 $2$ 号线从 $6$ 到 $3$，乘坐 $1$ 号线从 $3$ 到 $2$，再乘坐 $3$ 号线从 $2$ 到 $4$，最后乘坐 $4$ 号线从 $4$ 到 $7$。

如上，四个人分别贡献了 $2, 2, 1, 4$ 的客流量，答案为 $9$。

样例 2 如图：

相比样例 1，
乘客 $2$ 可以选择另外一条路线，即乘坐 $4$ 号线从 $4$ 到 $8$，再乘坐 $2$ 号线从 $8$ 到 $3$，也是换乘一次的；
乘客 $4$ 可以选择另外一条换乘次数更少的的路线：乘坐 $4$ 号线从 $7$ 到 $8$，再乘坐 $2$ 号线从 $8$ 到 $6$，只换乘了一次。

总客流量为 $2 + 2 + 1 + 2 = 7$。

样例 3 如图：

相比样例 1，乘客 $2$ 和 $4$ 的出行路径不是通路，不会计入客流量。

总客流量为 $2 + 0 + 1 + 0 = 3$。

---

设车站 $i$ 停靠的线路数为 $\mathrm{siz}_i$。
对于所有数据：

• $2 \le N \le 10^5$；
• $1 \le M \le 1000$；
• $1 \le P \le 100$；
• $1 \le \mathrm{siz}_i \le 50$。

---

本题采用捆绑测试。

No.	Constraints	Score
$1$	$N, P \le 5;\ M \le 3$	$10$
$2$	$k_i = 2$	$20$
$3$	$N, M \le 50;\ P \le 10$
$4$	$M \le 500;\ P \le 10$
$5$	No further constraints	$30$

---

由于读入量较大，请勿不关流同步使用 cin。

你可以通过 std::ios::sync_with_stdio(false) 来关闭 cin 的流同步。

你也可以使用以下快速读入模板，支持读入 int 范围内的非负整数。

int readInt() {
	int ret = 0; char o;
	while (!isdigit(o = getchar()));
	do ret = ret * 10 + (o ^ 48);
	while (isdigit(o = getchar()));
	return ret;
}

---

• Idea: 南桥汽车站
• Solution: 南桥汽车站
• Code: 南桥汽车站
• Data: 南桥汽车站