解题思路

• 把“地铁线路上的连续乘坐”看作在同一条线路内行走不增加换乘次数，只有从一条线路换到另一条线路才计一次换乘。

• 建模为线路图：每条地铁线路是一条图上的点；若两条线路在某个站有交集，则两点之间连一条边。

• 查询从起点站 s 到终点站 t 的最少换乘次数：

  • 找出包含 s 的所有线路作为起点集合，包含 t 的所有线路作为目标集合。
  • 若两集合有交集，答案为 0；否则在线路图上对起点集合做BFS，第一次到达目标集合中的任意线路时的层数即最少换乘次数。

• 关键算法：建图 + BFS 最短路（无权图）。

• 实现要点：

本题为2025年10月22日华为机考原题

华为机考的介绍点击这里

题目内容

在一个城市的地铁交通网络，有 $M$ 条地铁线路和 $N$ 个地铁站点，每个地铁站都是一个节点，从 $0$开始按照顺序编号，如果两条不同的地铁线路在同一个地铁站点交汇，表示可以在这个地铁站点从一条地铁线路换乘到另一条线路，即两条线路上出现相同的站点编号意味着是个换乘点，这个地铁站点对于两条地铁线路来说是连通的。现在根据给定需要查询的地铁行程路线（从起始地铁站点到终点地铁站点），请给出这些地铁行程路线的最少地铁线路换乘次数。

输入描述

第一行包含三个整数 $n、m$ 和 $k$ ，分别表示站点数量、地铁线路数量和需要查询的起点站和终点站的组合数量。

接下来 $m$ 行，每行描述一条地铁线路，首先是一个整数 $n$ 表示该线路上的站点数量，然后是 $n$ 个整数，表示线路上的站点编号(从 $0$ 开始)。

接下来 $k$ 行，每行包含两个整数 $s$ 和 $t$ ，表示一次查询的起点站和终点站。$n,m,k$ 取值范围在 $[0,1000)$

输出描述

对于每次查询，输出一个整数，要示从起点站到终点站的最少换乘次数，如果无法到达，则输出 $-1$ .

样例1

输入

3 2 2
2 0 1
2 0 2
0 2
0 1

输出

0
0

说明

从站点 $0$ 到站点 $2$ ，无需换乘直达

从站点 $0$ 到站点 $1$ ，无需换乘直达

样例2

输入

4 2 2
3 0 1 2
3 1 2 3
0 3
1 3

输出

1
0

说明

从站点 $0$ 到站点 $3$ ，最少需要换乘 $1$ 次(例如，从 $0$ 到 $1$ (线路 $1$ )，然后换乘到线路 $2$ 的 $2$ 站，再到 $3$ 站)；从站点 $1$ 到站点 $3$ ，不需要换乘(都在线路 $2$ 上)。