Overview

This problem uses the property that “in a single ride, you can travel to any bus stop within the same route” and asks you to find the minimum number of rides using BFS on bus stops as vertices.
The key point is that each route should be used only once, since expanding the same route multiple times would be too slow.

Analysis

The two important observations are:

1. When you have reached bus stop \(u\) with \(d\) rides,
   by taking any single route \(r\) passing through \(u\), you can reach all bus stops on that route in \(d+1\) rides.
2. After expanding route \(r\) once (relaxing all bus stops on that route),
   expanding the same route \(r\) again from a different bus stop essentially provides no new information and is wasteful.

If you naively traverse “from each bus stop, all routes passing through it, and then all bus stops on each of those routes” every time, you would scan the same route repeatedly, leading to extremely poor worst-case performance.
Instead, we maintain used_route[r] and process each route only the first time it is used.

This way, each bus stop enters the queue only when necessary, and each route scans through all its stops only once, allowing the entire process to run efficiently within the constraints.

Algorithm

1. Build the following from the input:
   • routes[r]: list of bus stops that route \(r\) passes through
   • stop_to_routes[s]: list of route numbers passing through bus stop \(s\) (reverse lookup)
2. Let dist_stop[s] be “the minimum number of rides to reach bus stop \(s\)”, initialized to \(\infty\), with dist_stop[S]=0.
3. Perform BFS using a queue:
   • Dequeue bus stop u. If u==T, output the distance and terminate.
   • For each route r passing through u, if it has not been used yet, mark it as used.
   • For each bus stop v on route r, if dist_stop[v] > dist_stop[u] + 1, update it and enqueue v.
4. If BFS finishes without reaching T, output -1.

This BFS expands layer by layer with “one ride” as exactly one unit of cost, so the first time T is reached gives the minimum number of rides.

Complexity

• Time complexity: \(O\!\left(N + \sum K_i\right)\) (roughly the same including input reading)
• Space complexity: \(O\!\left(N + M + \sum K_i\right)\)

(Reason)
Each route is expanded at most once due to used_route, and each expansion processes as many stops as that route contains, so the total processing on the route side is \(\sum K_i\) operations.

Implementation Notes

• By building stop_to_routes (stop → routes), you can immediately enumerate all routes available from the current location.

• used_route is the most critical component. Without it, the same route would be scanned repeatedly, causing slowdowns.

• The case S==T is also handled correctly, as u==T returns 0 right after BFS starts.

• It is safe to initialize the distance array with a sufficiently large value (INF) and use if dist_stop[v] > nd: for the update check.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, S, T = map(int, input().split())

    routes = []
    stop_to_routes = [[] for _ in range(N + 1)]

    for i in range(M):
        data = list(map(int, input().split()))
        k = data[0]
        stops = data[1:]
        routes.append(stops)
        for s in stops:
            stop_to_routes[s].append(i)

    INF = 10**18
    dist_stop = [INF] * (N + 1)
    used_route = [False] * M

    q = deque()
    dist_stop[S] = 0
    q.append(S)

    while q:
        u = q.popleft()
        d = dist_stop[u]
        if u == T:
            print(d)
            return

        for r in stop_to_routes[u]:
            if used_route[r]:
                continue
            used_route[r] = True
            nd = d + 1
            for v in routes[r]:
                if dist_stop[v] > nd:
                    dist_stop[v] = nd
                    q.append(v)

    print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.