星际跃迁网络

[编程题]星际跃迁网络

热度指数：289 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个广袤的宇宙中，存在一个由 $N$ 个星系组成的星际网络，星系编号从 $0$ 开始。

探险家们依赖 $M$ 条不同的“跃迁航线”在星系间穿梭。每条跃迁航线都连接着多个星系。

如果两条不同的跃迁航线都经过同一个星系，那么探险家就可以在该星系从一条航线切换到另一条，我们称之为一次“航线换乘”。

现在，给定一系列的星际旅行任务，每个任务包含一个起始星系和一个目标星系，请计算出完成每个任务所需的最少航线换乘次数。

输入描述:

第一行包含三个整数 、 和 ，分别代表星系的总数量、跃迁航线的总数量以及需要查询的旅行任务数量。

接下来  行，每行描述一条跃迁航线。
行首是一个整数 ，表示该航线连接的星系数量，随后是  个整数，代表这些星系的编号。

再接下来  行，每行包含两个整数  和 ，分别代表一个旅行任务的起始星系和目标星系。

所有变量的取值范围均为 。

输出描述:

对于每个查询任务，输出一个整数，即从起始星系  到目标星系  所需的最少换乘次数。
如果无法从  到达 ，则输出 。

示例1

输入

19 9 6
5 5 8 10 13 18
4 1 5 7 9
2 9 10
7 1 5 6 7 12 15 16
7 0 4 6 8 13 14 17
6 3 4 10 15 16 18
9 2 3 6 7 8 9 12 14 17
5 1 3 7 9 11
9 3 5 6 8 9 10 14 15 18
2 5
1 8
10 6
5 12
5 7
17 8