\( \def \ra {\rightarrow} \)
テレポータの行き先を超頂点 \(X \not\in N\) とおく． \(X\) を頂点として加えたグラフを考える． これにより，テレポータの行き先を保留した状態でグラフを構成できる． \(X\) の行き先を \(i\) としたいときは， コスト 0 の辺 \(i \rightarrow X\) を追加すればよい． すでにコスト 1の辺 \(i \rightarrow X\) があるかもしれないが， 最短経路を計算するときはコスト 0 の方が採用されるので，無駄な辺が残っていても問題ない．
各 \(i \in N \) に対して，テレポータの行き先を \(i\) としたときの \(0 \rightarrow N-1\) の最短コストを求めたい． 多くの計算は使いまわせそうなので，その方針でいく． \(i\) を固定して考える．
使いまわすために，最短経路を場合分けして求める． テレポータを使うか使わないかで場合分けするのだが， イメージとしては，
\(0 \ra X\)の近傍の頂点\(a \ra X\)の近傍の頂点\(b \ra N-1\)
というルート，または
\(0 \ra N-1\) をテレポータを使わないで行く
に分ける．
\(a = i\) のときは \(a \ra X\) のコストは 0, そうでなければ 1. \(X \ra b\) も同様．
この場合分けにより，計算を使いまわして求めることが出来る．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m; cin >> n >> m;
vvll to(n);
vll s;
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
if(a!=-1){
to[a].push_back(b);
to[b].push_back(a);
}else{
s.push_back(b);
}
}
vll d0(n, INFL), d1(n, INFL);
auto bfs = [&](ll src, vll &dis) -> void {
queue<ll> que;
que.push(src);
dis[src] = 0;
while(!que.empty()){
ll cu = que.front(); que.pop();
fore(ne, to[cu]) if(dis[ne] == INFL){
dis[ne] = dis[cu] + 1;
que.push(ne);
}
}
};
bfs(0, d0);
bfs(n-1, d1);
ll mi0 = INFL, mi1 = INFL;
fore(x,s){
chmin(mi0, d0[x]);
chmin(mi1, d1[x]);
}
rep(i,n){
ll ans = INFL;
chmin(ans, d0[n-1]);
chmin(ans, mi0 + 1 + d1[i]);
chmin(ans, d0[i] + 1 + mi1);
chmin(ans, mi0 + 2 + mi1);
if(ans >= INFL) ans = -1;
cout << ans << " ";
}
return 0;
}
