The transfer ticket

Two firms run the late buses, and a transfer ticket holds only if you change firm at every change of bus. From the terminus, how far is everything?

The problem

Stops are numbered 0 to stops - 1; the terminus is stop 0. Northline and Cityhop each publish their own one-way legs [u, v], and both may run one between the same pair.

A ticket stays valid only while consecutive legs are run by different firms: after a Northline leg the next must be Cityhop, and the other way round. The first leg out may be either.

For every stop, report the fewest legs of a valid journey from the terminus, -1 if none reaches it; the terminus itself is 0.

Input. stops — an integer. northline, cityhop — lists of legs [u, v].

Output. A list of stops integers: fewest legs to each stop, or -1.

Example.

stops = 3, northline = [[0, 1], [1, 2]], cityhop = []   ->  [0, 1, -1]

One Northline leg reaches stop 1. Stop 2 needs a second Northline leg, which the ticket forbids, so it is unreachable though the legs form a path.

A second example, where the arriving firm decides what comes next:

stops = 5,
northline = [[0, 1], [2, 3]],
cityhop   = [[0, 3], [1, 2], [3, 4]]
  ->  [0, 1, 2, 1, 4]

Stop 3 is one Cityhop leg out, but that arrival dead-ends: the next leg must be Northline and none leaves stop 3. Arriving on Northline takes three legs, so stop 4 is 4 away.

Constraints.

• 1 <= stops <= 10^5
• 0 <= len(northline) + len(cityhop) <= 2 × 10^5
• legs may be duplicated, and u may equal v

Hints

Approach

Brute force

Extend every valid journey a leg at a time, keeping the shortest to each stop. Journeys branch at every stop and may revisit them, so uncapped this never ends; capped at 40 legs, two legs out of each stop gives 2^40, about 1.1 × 10^12 journeys.

The insight

What you are searching is not the stop but the pair (stop, firm that brought you there): 2 × stops states, each with one legal set of legs out.

Once the state carries the arriving firm, the rule stops depending on history: from (u, Northline) the only moves are Cityhop legs out of u. Every leg costs one, so a state's first arrival is its shortest. Seeding the terminus under both firms lets the first leg be either.

Algorithm

1. Build two adjacency lists, one per firm.
2. Fill best[firm][stop] with infinity, set both terminus states to 0, queue them.
3. Pop (stop, arrived_on); the next firm is the other. Each of its legs out of stop still at infinity takes one more than the popped distance and is pushed.
4. Each stop's answer is the smaller of its two entries, or -1 if both are still infinite.

Complexity

Time O(stops + legs) — each of the 2 × stops states pops once at most, and a leg is read only from the state that may use it: 3 × 10^5 steps, not 10^12 journeys. Space O(stops + legs) — the lists and table.

Solution

"""The transfer ticket — BFS over (stop, operator that brought you there), not over stops."""

from collections import deque

NORTHLINE, CITYHOP = 0, 1


def solve(stops, northline, cityhop):
    legs = [[[] for _ in range(stops)], [[] for _ in range(stops)]]
    for u, v in northline:
        legs[NORTHLINE][u].append(v)
    for u, v in cityhop:
        legs[CITYHOP][u].append(v)

    INF = float('inf')
    # best[operator][stop]: fewest legs to stand at stop having just ridden that operator.
    best = [[INF] * stops, [INF] * stops]
    best[NORTHLINE][0] = best[CITYHOP][0] = 0
    # Seeding the terminus under both firms is what lets the first leg be either.
    queue = deque([(0, NORTHLINE), (0, CITYHOP)])

    while queue:                     # invariant: states leave the queue in non-decreasing legs
        stop, arrived_on = queue.popleft()
        next_operator = 1 - arrived_on   # the ticket rule: consecutive legs never share an operator
        for onward in legs[next_operator][stop]:
            if best[next_operator][onward] == INF:
                best[next_operator][onward] = best[arrived_on][stop] + 1
                queue.append((onward, next_operator))

    out = []
    for stop in range(stops):
        fewest = min(best[NORTHLINE][stop], best[CITYHOP][stop])
        out.append(-1 if fewest == INF else fewest)
    return out

TESTS = [
    ((3, [[0, 1], [1, 2]], []), [0, 1, -1]),
    ((3, [[0, 1]], [[1, 2]]), [0, 1, 2]),
    ((5, [[0, 1], [2, 3]], [[0, 3], [1, 2], [3, 4]]), [0, 1, 2, 1, 4]),
    ((5, [[0, 1], [1, 2], [2, 3], [3, 4]], [[1, 2], [2, 3], [3, 4]]), [0, 1, 2, 3, 4]),
    ((2, [], []), [0, -1]),
    ((4, [[0, 1], [0, 2]], [[2, 3]]), [0, 1, 1, 2]),
    ((2, [], [[0, 1]]), [0, 1]),
    ((1, [[0, 0]], []), [0]),
    ((3, [[0, 1], [0, 1]], [[1, 2]]), [0, 1, 2]),
]

Pitfalls

• Marking a stop visited rather than a state. Stop 3 of the second example is first reached on Cityhop at 1 leg, a dead end; a sweep marking stops drops the Northline arrival and reports -1 for stop 4.
• Seeding the terminus under one firm only. The first leg is forced to be Cityhop, and the first example returns [0, -1, -1].
• Merging both lists into one. The alternation vanishes and the first example degrades to plain hop counts, [0, 1, 2].

Variants

• Blue mould on the bench — the same sweep from many seeds, with the cell as the whole state.
• Crossing the mudflats — the same sweep on a grid.