声明： 记 $u_i = 0$ 的 $v_i$ 为关键点

不难发现，本题是最短路题。暴力 is 没有前途的，考虑连边（叫做新边）的影响。

显然，连边后我既可以走新边，也可以不走。肯定要记录以源点（$1$）为源点的最短路，以终点（$n$）为源点的最短路，叫做 $dis_1, dis_n$。

于是，后面再维护 $min_1, min_n$ 叫做 $1$ 到 关键点的最短距离，$n$ 到 关键点的最短距离。

令当前钦定的 $u_i$ 连边为 $j$

答案有以下几种：

1. 不走，$ans = dis_n$

2. 从 $1$ 到关键点到 $j$ 再到 $n$, $ans = min_1 + 1 + dis_n$。

3. 从 $1$ 到 $j$ 到 关键点 再到 $n$ , $ans = min_n + 1 + dis_1$

4. 从 $1$ , 到关键点再到另一个关键点 再到 $n$。$ans = min_1+min_n+2$

可以证明，仅有以下四种。