Fewest lines to reverse

Every line in this network runs one way: (u, v) means trains go from u to v only. The railway can reverse any line, so that trains run from v to u instead. Return the fewest lines that must be reversed so that a train can go from station s to station t. Return -1 if even reversing lines cannot join them.

lines = [(0, 1), (2, 1), (2, 3), (4, 3)]
fewest_reversals(5, lines, 0, 4)              # 2
fewest_reversals(3, [(0, 1), (1, 2)], 0, 2)   # 0
fewest_reversals(4, [(0, 1), (2, 3)], 0, 3)   # -1

In the first call, go 0 → 1 along its line, then reverse 2 → 1 to go 1 → 2, then 2 → 3, then reverse 4 → 3. A line may be listed more than once, and a line may join a station to itself.

Limits

• Up to 100,000 stations and 200,000 lines.
• Aim for O(V + E). The big tests have 4 seconds each.