towns towns along a highway, numbered from 0 to towns - 1. At first the only roads are one-way roads from each town i to town i + 1.
New one-way roads open one at a time: shortcuts[j] = [u, v] is a road from town u to town v, where u < v. A new road may also duplicate an existing road u → u + 1.
After each road opens, find the fewest roads needed to travel from town 0 to town towns - 1. Return these numbers as a list, one per new road, in the order the roads open.towns=6, shortcuts=[[1, 4], [3, 5], [0, 3]] → [3, 3, 2]
After the road 1 → 4, the route 0 → 1 → 4 → 5 takes 3 roads. The road 3 → 5 does not help. After 0 → 3, the route 0 → 3 → 5 takes 2 roads.
towns=4, shortcuts=[[0, 3], [1, 3]] → [1, 1]
The very first road leads straight from 0 to 3, and the answer stays 1 after that.
towns=6, shortcuts=[[1, 4], [3, 5], [0, 3]]
[3, 3, 2]
Run checks the first 3 tests in your browser. Submit checks all 67 tests on the server, hidden ones included.