/* -*- coding: utf-8 -*- * * 3463.cc: No.3463 Beltway - yukicoder */ #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; const int MAX_M = 200000; /* typedef */ using qi = queue; using vi = vector; using vb = vector; using vvi = vector; using pii = pair; using vpii = vector; using si = stack; /* global variables */ vpii nbrs[MAX_N]; pii es[MAX_M]; int ds[MAX_N], gids[MAX_N]; vi gnbrs[MAX_N]; /* subroutines */ void bcc_visit(const vpii nbrs[], int v, int ei, vi& brdg, vvi& tecomp, si& roots, si& S, vb& inS, vi& num, int& time) { num[v] = ++time; S.push(v); inS[v] = true; roots.push(v); for (const auto [w, wei]: nbrs[v]) { if (num[w] == 0) bcc_visit(nbrs, w, wei, brdg, tecomp, roots, S, inS, num, time); else if (ei != wei && inS[w]) while (num[roots.top()] > num[w]) roots.pop(); } if (v == roots.top()) { brdg.push_back(ei); tecomp.push_back(vi()); for (;;) { int w = S.top(); S.pop(); inS[w] = false; tecomp.back().push_back(w); if (v == w) break; } roots.pop(); } } void calc_bcc(const int n, const vpii nbrs[], vi& brdg, vvi& tecomp) { vi num(n); vb inS(n); si roots, S; int time = 0; for (int u = 0; u < n; u++) if (num[u] == 0) { bcc_visit(nbrs, u, -1, brdg, tecomp, roots, S, inS, num, time); brdg.pop_back(); } } int bfs(int n, int st, int gl) { fill(ds, ds + n, -1); ds[st] = 0; qi q; q.push(st); while (! q.empty()) { int u = q.front(); q.pop(); if (u == gl) return ds[u]; for (auto [v, ei]: nbrs[u]) if (ds[v] < 0) ds[v] = ds[u] + 1, q.push(v); } return -1; } /* main */ int main() { int n, m, st, gl; scanf("%d%d%d%d", &n, &m, &st, &gl); st--, gl--; for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; nbrs[u].push_back({v, i}); nbrs[v].push_back({u, i}); es[i] = {u, v}; } int gd = bfs(n, st, gl); if (gd < 0) { puts("-1"); return 0; } vi brdg; vvi tcmp; calc_bcc(n, nbrs, brdg, tcmp); //for (auto ei: brdg) printf(" %d", ei); putchar('\n'); int gn = tcmp.size(); for (int i = 0; i < gn; i++) for (auto u: tcmp[i]) gids[u] = i; for (auto ei: brdg) { auto [u, v] = es[ei]; int gu = gids[u], gv = gids[v]; gnbrs[gu].push_back(gv); gnbrs[gv].push_back(gu); } int gst = gids[st], ggl = gids[gl]; fill(ds, ds + gn, -1); ds[gst] = 0; qi q; q.push(gst); while (! q.empty()) { int u = q.front(); q.pop(); if (u == ggl) break; for (auto v: gnbrs[u]) if (ds[v] < 0) ds[v] = ds[u] + 1, q.push(v); } printf("%d\n", gd - ds[ggl]); return 0; }