C. 下一站:奥体中心

    传统题 400ms 512MiB

下一站:奥体中心

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

大样例下载

题目背景

 Codeland\textrm{ Codeland} 有一个庞大的地铁网。

题目描述

 Codeland\textrm{ Codeland} 有编号为 1∼n1 \sim n 的 nn 座地铁站和编号为 1∼m1 \sim m 的 mm 条双向地铁线路。

每个地铁站可以有多条线路经过。如果两条线路经过同一个车站,则两条线路可以只用一次换乘到达。

如果两个车站在同一条线路上,则两座车站间不用换乘也可以到达。

小 S 现在要出行 qq 次,每次要从 xx 到 yy。

因为他不想换乘,所以他希望换乘次数尽可能少。

特别的,如果出行的起始站或终点站时换乘站,他可以选择任意一个从经过该站的地铁线路出发或到达,而无需换乘。

请回答他,每次出行最少要几次换乘。

如果两个车站间没有被直接或间接的相连,输出 0。

输入格式

第一行三个数 n,m,qn,m,q ,含义如题所示。

接下来 nn 行,依次表示 1∼n1 \sim n 站的信息,每行第一个数为 kk,表示经过这个站的线路数量,接下来 kk 个数依次为经过这个站的线路编号。

接下来 qq 行,每行两个整数 x,yx,y ,表示出行的起点和终点。

输出格式

qq 行,每行一个整数,表示每次询问的答案。

Samples

7 3 3
1 1
2 1 2
1 1
2 2 3
1 2
1 3
1 3
2 7
1 6
2 3
1
2
0

样例解释

Codeland\textrm{Codeland} 地铁线网图。

从 22 号站到 77 号站,需要乘坐 22 号线,然后在 33 号站换乘 33 号线,最后在 77 号站下车,共换乘 11 次。

从 11 号站到 66 号站,需要乘坐 11 号线,然后在 22 号站换乘 22 号线,然后在 33 号站换乘 33 号线,最后在 66 号站下车,共换乘 22 次。

从 22 号站到 33 号站,需要乘坐 22 号线,然后在 33 号站下车,无需换乘。

数据范围

对于 50%50\% 的数据 1≤n≤501 \le n \le 50。

对于 100%100\% 的数据,1≤n≤5×1051 \le n \le 5 \times 10^5,1≤m≤301 \le m \le 30,1≤q≤1041 \le q \le 10^4 且输入数据合法。

提示

输入量较大,注意读入方式对程序常数因子的影响。

2026-07-09

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-7-9 7:30
结束于
2026-7-9 10:06
持续时间
2.6 小时
主持人
参赛人数
22