import sys
from collections import defaultdict, deque
N, M, K = map(int, sys.stdin.readline().split())
adj = defaultdict(lambda: [])
INF = 0x3F3F3F3F
'''
# 0-1 BFS超时
for i in range(M):
    stars = list(map(int, sys.stdin.readline().split()))
    adj[N + i] = [(j, 1) for j in stars[1:]]
    for j in stars[1:]:
        adj[j].append((N + i, 0))

# print(adj)
def bfs_01(s, t):
    dq = deque([s])
    visited = [False] * (M + N)
    dists = [INF] * (M + N)
    visited[s] = True
    dists[s] = 0
    while dq:
        root = dq.popleft()
        for child, weight in adj[root]:
            if visited[child]:
                continue
            if weight:
                dq.append(child)
            else:
                dq.appendleft(child)
            if dists[child] > dists[root] + weight:
                dists[child] = dists[root] + weight
            visited[child] = True
            if child == t:
                break
            # if dists[child] > dists[root] + weight:
            #     dists[child] = dists[root] + weight
            #     if weight:
            #         dq.append(child)
            #     else:
            #         dq.appendleft(child)
            #     if child == t:
            #         break
        # print(root, adj[root], dists)
    return dists[t]
query = list(map(int, sys.stdin.read().split()))
res = []
for k in range(K):
    s, t = query[(2*k):(2*k+2)]
    dist = bfs_01(s, t)
    if dist>=INF:
        res.append(-1)
    else:
        res.append(dist-1)
print('\n'.join(map(str, res)))
'''

star_line_map = defaultdict(lambda : [])
for i in range(M):
    stars = list(map(int, sys.stdin.readline().split()))
    for j in stars[1:]:
        star_line_map[j].append(i)

INF = 0x3F3F3F3F
'''
# Floyd算法会超时
line_dist = [[INF] * M for _ in range(M)]
for i in range(M):
    line_dist[i][i] = 0
for star, lines in star_line_map.items():
    l = len(lines)
    for i in range(l):
        for j in range(i+1, l):
            line_dist[lines[i]][lines[j]] = 1
            line_dist[lines[j]][lines[i]] = 1
for k in range(M):
    for i in range(M):
        for j in range(M):
            line_dist[i][j] = min(line_dist[i][j], line_dist[i][k] + line_dist[k][j])

for k in range(K):
    s, t = map(int, sys.stdin.readline().split())
    min_jump = INF
    for l1 in star_line_map[s]:
        for l2 in star_line_map[t]:
            if line_dist[l1][l2] < min_jump:
                min_jump = line_dist[l1][l2]
    if min_jump >= INF:
        print(-1)
    else:
        print(min_jump)
'''
for star, lines in star_line_map.items():
    l = len(lines)
    for i in range(l):
        for j in range(i+1, l):
            adj[lines[i]].append(lines[j])
            adj[lines[j]].append(lines[i])
def bfs_m(starts, targets):
    line_dist = [INF] * M
    visited = [False] * M
    for s in starts:
        line_dist[s] = 0
        visited[s] = True
    dq = deque(starts)
    dist = -1
    while dq:
        root = dq.popleft()
        if root in targets:
            dist = line_dist[root]
            break
        for child in adj[root]:
            if not visited[child]:
                line_dist[child] = line_dist[root] + 1
                visited[child] = True
                dq.append(child)
    return dist

query = list(map(int, sys.stdin.read().split()))
res = []
for k in range(K):
    s, t = query[(2*k):(2*k+2)]
    dist = bfs_m(star_line_map[s], star_line_map[t])
    print(dist)
print('\n'.join(map(str, res)))
  • N个站点，M条线，查询次数K
  • 构造线的连接图，
  • 使用Folyd算法搜索所有线之间的换乘数目（O(M^3)）;然后根据S，T所在的线查询，因为每个站点可能位于好几条线上，需要循环检索，复杂度O(K*M^2)，会超时。假如每个被查询的站点只位于很少的几条线，比如最多位于2条线上，那么查询复杂度为O(4K)，当K极大时，用Floyd算法预存可以降低常数项。
  • 使用多源BFS查询，每次查询O(M)，总复杂度为O(K*M)
  • 构造点和线的连接图：使用0-1 BFS，每次查询O(M+N)，总复杂度为O(K*(M+N))，实测会超时