A shortest route

The network is as in P1: stations 0 to n − 1, and lines (u, v) that run both ways. Return a route from station s to station t that uses the fewest lines, as a list of stations that starts with s and ends with t. Return None if no route exists.

edges = [(0, 5), (5, 6), (0, 1), (1, 2), (2, 3), (3, 4), (4, 6)]
route(7, edges, 0, 6)     # [0, 5, 6]
route(3, [(0, 1)], 0, 2)  # None
route(3, [(0, 1)], 1, 1)  # [1]

When several routes are equally short, any of them is accepted. The tests check that your list is a route (each pair of stations next to each other in it is joined by a line) and count its lines.

Limits

• Up to 500,002 stations and 500,001 lines.
• Routes can be 100,000 lines long, so a recursive search is too deep. One station can have 500,000 neighbours waiting in the queue at once. The big tests have 3 seconds each, and 4 for that one.