An undirected, connected graph has n vertices labeled 1 through n. Each pair in edges connects two vertices, and traversing any edge takes time minutes.
Every vertex has a synchronized traffic light. Starting green at minute 0, all lights switch color every change minutes: green for the first interval, red for the next, and so on. You may arrive at any time, but may leave only on green. If the light is green, you must leave immediately; if it is red, you must wait until it turns green.
Starting at vertex 1 at minute 0, return the second smallest distinct time at which you can arrive at vertex n. You may revisit any vertex or edge, including vertices 1 and n. A second arrival time must be strictly greater than the minimum, even when multiple routes achieve the minimum.
Example 1:
Input: n = 3
edges = [[1,2],[2,3],[1,3]]
time = 2
change = 3
Output: 4Explanation: The direct edge 1 → 3 arrives at minute 2. The two-edge route 1 → 2 → 3 leaves vertex 2 at minute 2, while the light is still green, and arrives at minute 4. This is the next distinct arrival time.
Example 2:
Input: n = 3
edges = [[1,2],[2,3]]
time = 2
change = 2
Output: 14Explanation: The fastest walk 1 → 2 → 3 arrives at minute 6: travel for 2 minutes, wait until minute 4, then travel for 2 more. The next possible walk takes four edges, such as 1 → 2 → 1 → 2 → 3. Departures occur at minutes 0, 4, 8, and 12, so it arrives at minute 14.
Example 3:
Input: n = 4
edges = [[1,2],[2,4],[1,3],[3,4]]
time = 2
change = 100
Output: 8Explanation: Both two-edge routes arrive at minute 4, which counts as one distinct time. There is no three-edge walk to vertex 4. A four-edge walk such as 1 → 2 → 1 → 3 → 4 arrives at minute 8, with all departures on green.
Constraints:
2 <= n <= 10000n - 1 <= edges.length <= min(20000, n * (n - 1) / 2)- Each edge contains two distinct integer labels between
1andn. - Edges are unique as undirected pairs, and the graph is connected.
1 <= time, change <= 1000