P7500 「HMOI R1」地铁客流

一座城市的地铁客流量是非常重要的指标，它体现了这座城市正在不断流动着的人口数量。无论通勤还是旅游，都会给这座城市的经济带来活力。 疫情期间各地地铁客流惨淡，甚至有部分城市地铁停运。现在疫情态势好转，各地陆续复工复产，地铁客流量大小也是判断城市复工复产、经济恢复率的重要参考。

天穹市的地铁系统由 $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)$，表示一位乘客的出行起终点。

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

样例解释： - 默认乘客会选择换乘次数最少的路径。 - 边上的数字表示所在地铁线路的编号。 样例 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$ | $20$ | | $4$ | $M \le 500;\ P \le 10$ | $20$ | | $5$ | No further constraints | $30$ | ------------ 由于读入量较大，请勿不关流同步使用 `cin`。 你可以通过 `std::ios::sync_with_stdio(false)` 来关闭 `cin` 的流同步。 你也可以使用以下快速读入模板，支持读入 `int` 范围内的非负整数。 ```cpp 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: 南桥汽车站