n towns along a highway, numbered 0 to n - 1. Initially there is a one-way road from every town i to town i + 1 (for all 0 ≤ i < n - 1).
Express roads open one by one: shortcuts[i] = [u, v] is a new one-way road from town u to town v, where u < v (it may duplicate an existing road). Express roads never cross: there are no two of them, [a, b] and [c, d], with a < c < b < d. Any two express roads are either nested or disjoint (sharing an end is allowed).
After each express road opens, find the fewest roads on a trip from town 0 to town n - 1. Return these numbers in the order the express roads open.n=6, shortcuts=[[1, 4], [0, 1], [0, 4], [4, 5]] → [3, 3, 2, 2]
With the 1 → 4 road, the trip 0 → 1 → 4 → 5 takes three roads. The 0 → 1 express road repeats an existing road and changes nothing. With 0 → 4, two roads are enough: 0 → 4 → 5. The 4 → 5 express road also duplicates an ordinary one.
n=5, shortcuts=[[0, 4], [1, 3]] → [1, 1]
The very first road goes straight from start to finish, and the answer stays the same after that.
n=6, shortcuts=[[1, 4], [0, 1], [0, 4], [4, 5]]
[3, 3, 2, 2]
Run checks the first 3 tests in your browser. Submit checks all 15 tests on the server, hidden ones included.