A bidirectional connected graph consists of n vertices labeled from $1$ to n. You are given a $2$D integer array edges where each edges[i] = [u_i, v_i] represents a bidirectional edge between vertex u_i and vertex v_i. Each pair of vertices is connected by at most $1$ edge, and there are no self loops.

Traversing any edge takes time minutes.

Every vertex has a traffic signal that alternates between green and red simultaneously every change minutes. All signals begin green at time $0$. The signals change to red at change minutes, back to green at $2 \times$ change minutes, and continue alternating indefinitely. You can only depart from a vertex when its signal is green. You may wait at any vertex for any amount of time.

Return the second minimum time in minutes required to travel from vertex $1$ to vertex n.

Note:

• A path is allowed to visit any vertex or cross any edge multiple times.

• The second minimum value is defined as the strictly smallest value that is greater than the minimum time.

Constraints:

• $2 \leq$ n $\leq 10^4$

• n $- 1 \leq$ edges.length $\leq \min(2 \times 10^4$, n $\times$ ( n $- 1) / 2)$

• edges[i].length $= 2$

• $1 \leq$ u_i, v_i $\leq$ n

• u_i $\neq$ v_i

• There are no duplicate edges.

• Each vertex can be reached directly or indirectly from every other vertex.

• $1 \leq$ time, change $\leq 10^3$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.