Overview

If we consider each bus route as a single vertex and think of “routes sharing the same bus stop can transfer between each other,” then the minimum number of rides can be found as the shortest distance on this route graph.
However, naively adding all edges between routes is too expensive, so the key point is to perform BFS via bus stops.

Discussion

In this problem, riding a bus once allows you to move to “any other bus stop that the route passes through.”
In other words, once you board a route, you can reach all bus stops on that route.

Key Insight 1: Use “routes” rather than “bus stops” as states

For example, if you are riding route \(i\), you can go to any bus stop on that route.
Therefore, rather than tracking “which bus stop am I currently at,” it is more natural to track which route am I currently riding.

• Using route \(i\) = riding that route once
• Two routes sharing the same bus stop can transfer between each other

Thus,

• Starting points: all routes passing through \(S\) (distance \(1\) since this is the first ride)
• Goal: reach any route that passes through \(T\)

and the answer becomes “the number of route transfers.”

Key Insight 2: Explicitly building the route graph is too expensive

Consider making routes into vertices and adding edges between routes that share the same bus stop.
However, if many routes pass through a certain bus stop, that single stop generates a huge number of edges.

For example, if \(d\) routes pass through a certain bus stop, up to \(O(d^2)\) edges are needed among them.
Doing this for all bus stops is far too slow in the worst case.

Key Insight 3: Transition via bus stops “only when needed”

Instead, we only maintain:

• Which bus stops each route passes through
• Which routes pass through each bus stop

and look up transitions only when needed during BFS.

When route \(r\) is dequeued during BFS, we look at each bus stop stop on that route,
and transition to other routes that pass through that stop.

Why used_stop is necessary

Examining the same bus stop multiple times creates significant waste.
For example, if many routes pass through a single bus stop, every time we visit that stop we would redundantly scan the same list of routes.

Therefore, for each bus stop:

• We perform the expansion to other routes only once, the first time.

Since BFS explores in order of increasing distance, the first time we reach a bus stop corresponds to the minimum number of rides to use that stop.
Even if we arrive at the same bus stop later, no better transitions can arise, so processing it once is sufficient.

Routes with only 1 stop cannot be used

According to the problem statement, when riding a route, you must get off at a bus stop “different from the one you are currently at.”
Therefore, routes that pass through only one bus stop cannot actually be used for travel.

In the code, such routes are excluded as transition targets.

Algorithm

We perform BFS as follows.

Preprocessing

Build: - routes[i]: the list of bus stops that route \(i\) passes through - stop_to_routes[x]: the list of routes that pass through bus stop \(x\)

At the same time:

• Whether route \(i\) contains \(T\): contains_t[i]
• If route \(i\) contains \(S\), set dist[i] = 1 and enqueue it into the BFS queue

However, when \(S = T\), the destination is reachable without riding any bus, so the answer is \(0\).

BFS

Let dist[i] be “the minimum number of rides needed to board route \(i\).”

1. Dequeue route r from the queue
2. If r passes through \(T\), then dist[r] is the answer
3. Look at each bus stop stop of route r
   • If used_stop[stop] = True already, skip it
   • Otherwise, set used_stop[stop] = True
   • For every route nr in stop_to_routes[stop], if it has not been visited yet, set dist[nr] = dist[r] + 1 and enqueue it

This explores routes in order of increasing number of rides.

Illustrative Example

For example:

• Route 1: \(\{1, 3, 5\}\)
• Route 2: \(\{5, 7\}\)
• \(S=1, T=7\)

Then:

• We can initially board route 1, so dist[1] = 1
• From route 1, we can reach bus stop 5
• We can transfer to route 2 which passes through bus stop 5, so dist[2] = 2
• Route 2 contains \(T=7\)

Therefore the answer is \(2\).

Complexity

Let \(\displaystyle L = \sum_{i=1}^{M} K_i\).

• Time complexity: \(O(N + M + L)\)
• Space complexity: \(O(N + M + L)\)

Reasoning

• The total number of times we scan bus stop lists across all routes is \(O(L)\)
• Each bus stop is expanded at most once due to used_stop
• Each “bus stop ↔ route” correspondence is essentially used at most once

Therefore, the overall algorithm runs in linear time.

Implementation Notes

• Handle \(S == T\) first and output \(0\)

• Use routes as BFS vertices, with starting routes having distance \(1\)

• Use used_stop to avoid expanding the same bus stop multiple times

• Routes with only one bus stop cannot be used for travel, so do not treat them as transition targets

• Since the input size is large, reading all at once with sys.stdin.buffer.read() is faster

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    S = next(it)
    T = next(it)

    if S == T:
        print(0)
        return

    routes = [[] for _ in range(M)]
    stop_to_routes = [[] for _ in range(N + 1)]
    contains_t = [False] * M
    dist = [-1] * M
    q = deque()

    for i in range(M):
        k = next(it)
        arr = [0] * k

        if k >= 2:
            has_s = False
            has_t = False
            for j in range(k):
                a = next(it)
                arr[j] = a
                stop_to_routes[a].append(i)
                if a == S:
                    has_s = True
                if a == T:
                    has_t = True
            contains_t[i] = has_t
            if has_s:
                dist[i] = 1
                q.append(i)
        else:
            arr[0] = next(it)

        routes[i] = arr

    used_stop = [False] * (N + 1)
    used_stop[S] = True

    while q:
        r = q.popleft()
        d = dist[r]

        if contains_t[r]:
            print(d)
            return

        for stop in routes[r]:
            if used_stop[stop]:
                continue
            used_stop[stop] = True
            for nr in stop_to_routes[stop]:
                if dist[nr] == -1:
                    dist[nr] = d + 1
                    q.append(nr)

    print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.