import std; void main () { int V, E, S, G; readln.read(V, E, S, G); S--, G--; auto A = new int[](E); auto B = new int[](E); foreach (i; 0 .. E) { readln.read(A[i], B[i]); A[i]--, B[i]--; } auto graph = new int[][](V); foreach (i; 0 .. E) { graph[A[i]] ~= B[i]; graph[B[i]] ~= A[i]; } // とりあえずBFSしてSからの距離をはかっておく、そして(u, v)であってdist[u] + 1 = dist[v]であるところのみ有向辺を貼る。 // そのグラフはDAGを成すので、その上でdp[i] := Sから最短のいずれかの道を辿ったとき、橋を最小何本通るかを求める // lowlinkで橋かどうかの判定ができるのでこれでOK auto dist = new int[](V); auto q = DList!(int)(); dist[] = int.max; q.insertBack(S); dist[S] = 0; while (!q.empty()) { auto pos = q.front(); q.removeFront(); foreach (to; graph[pos]) { if (dist[to] == int.max) { dist[to] = dist[pos] + 1; q.insertBack(to); } } } if (dist[G] == int.max) { writeln(-1); return; } // lowlink(窃盗 from https://algo-logic.info/bridge-lowlink/) bool[Tuple!(int, int)] bridge; auto used = new bool[](V); auto ord = new int[](V); auto low = new int[](V); int dfs (int id, int k, int par) { // id:探索中の頂点, k:dfsで何番目に探索するか, par:idの親 used[id] = true; ord[id] = k++; low[id] = ord[id]; int count = 0; // 子の数 foreach (e; graph[id]) { if (!used[e]) { count++; k = dfs(e, k, id); low[id] = min(low[id], low[e]); if (ord[id] < low[e]) bridge[tuple(min(id, e), max(id, e))] = true; // 条件を満たすので橋 } else if (e != par) { // eが後退辺の時 low[id] = min(low[id], ord[e]); } } return k; } { int k = 0; foreach (i; 0 .. V) { if (!used[i]) { k = dfs(i, k, -1); } } } auto memo = new int[](V); memo[] = -1; int dp (int x) { if (memo[x] != -1) { return memo[x]; } if (x == S) { return 0; } int ret = int.max; foreach (to; graph[x]) { if (dist[to] != dist[x] - 1) { continue; } int add = 0; auto e = tuple(min(x, to), max(x, to)); if (e in bridge) { add = 1; } ret = min(ret, dp(to) + add); } return memo[x] = ret; } writeln(dist[G] - dp(G)); } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }