在一个广袤的宇宙中，存在一个由 个星系组成的星际网络，星系编号从 开始。 探险家们依赖 条不同的“跃迁航线”在星系间穿梭。每条跃迁航线都连接着多个星系。 如果两条不同的跃迁航线都经过同一个星系，那么探险家就可以在该星系从一条航线切换到另一条，我们称之为一次“航线换乘”。 现在，给定一系列的星际旅行任务，每个任务包含一个起始星系和一个目标星系，请计算出完成每个任务所需的最少航线换乘次数。
输入描述:
第一行包含三个整数 、 和 ，分别代表星系的总数量、跃迁航线的总数量以及需要查询的旅行任务数量。接下来 行，每行描述一条跃迁航线。行首是一个整数 ，表示该航线连接的星系数量，随后是 个整数，代表这些星系的编号。再接下来 行，每行包含两个整数 和 ，分别代表一个旅行任务的起始星系和目标星系。所有变量的取值范围均为 。
输出描述:
对于每个查询任务，输出一个整数，即从起始星系 到目标星系 所需的最少换乘次数。如果无法从 到达 ，则输出 。
示例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
备注:
本题由牛友@Charles 整理上传
加载中...