// 各辺にコスト1を割り当て,x->y, x->z に流量 2 の最小費用流を流し,x->y のパスを固定して // 残りの頂点と辺で z->x, z->y に流量 2 の最小費用流を流す // 正当性なし(反例構成可能) #include #include #include #include using namespace std; #include // used_vs に含まれる頂点は使わずに,from -> to1 と from->to2 の点素なパスを構成する. // 両方のパスが構築できなければ empty vector の組を返す. pair, vector> twopaths(const vector> &to, const vector &used_vs, int from, int to1, int to2) { const int N = to.size(); const int gt = N * 2; atcoder::mcf_graph graph(gt + 1); vector valid_v(N, 1); for (auto i : used_vs) valid_v[i] = 0; valid_v[to1] = valid_v[to2] = 1; for (int i = 0; i < N; ++i) { graph.add_edge(i, i + N, valid_v[i], 0); } for (int i = 0; i < N; ++i) { for (auto j : to[i]) { int cost = 1; graph.add_edge(i + N, j, 1, cost); } } graph.add_edge(to1 + N, gt, 1, 0); graph.add_edge(to2 + N, gt, 1, 0); auto f = graph.flow(from + N, gt, 2); if (f.first < 2) return {{}, {}}; vector conn(N); for (auto e : graph.edges()) { if (e.flow) { if (e.to == gt) continue; int s = e.from % N, t = e.to % N; conn[s] ^= t; conn[t] ^= s; // ループがないので生えている辺の xor だけ持っておけば後で解が復元できる } } vector ret1, ret2; while (to1 != from) { ret1.push_back(to1); to1 = conn[to1]; conn[to1] ^= ret1.back(); } while (to2 != from) { ret2.push_back(to2); to2 = conn[to2]; conn[to2] ^= ret2.back(); } ret1.push_back(from); ret2.push_back(from); reverse(ret1.begin(), ret1.end()); reverse(ret2.begin(), ret2.end()); return {ret1, ret2}; } constexpr int inf = 1 << 20; int solve_fake_flow_sub(const vector> &to, const vector &banxy, int z, int x, int y) { auto [p1, p2] = twopaths(to, banxy, z, x, y); if (p1.empty()) return inf; return p1.size() + p2.size() + banxy.size() - 1; } int solve_by_flow_twice(const vector> &to, int x, int y, int z) { int N = to.size(); vector vs{x, y, z}; sort(vs.begin(), vs.end()); int ret = inf; do { auto [p01, p02] = twopaths(to, {}, vs[0], vs[1], vs[2]); if (p01.empty() or p02.empty()) continue; auto ban01 = p01, ban02 = p02; for (int t = 0; t < 2; ++t) { ban01.pop_back(), ban02.pop_back(); reverse(ban01.begin(), ban01.end()), reverse(ban02.begin(), ban02.end()); } ret = min(ret, solve_fake_flow_sub(to, ban01, vs[2], vs[0], vs[1])); ret = min(ret, solve_fake_flow_sub(to, ban02, vs[1], vs[0], vs[2])); } while (next_permutation(vs.begin(), vs.end())); return ret <= N ? ret : -1; } int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, M; int x, y, z; cin >> N >> M; cin >> x >> y >> z; --x, --y, --z; vector conn(N, vector(N, 1)); for (int i = 0; i < N; ++i) conn[i][i] = 0; while (M--) { int a, b; cin >> a >> b; --a, --b; conn[a][b] = conn[b][a] = 0; } vector> to(N); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (conn[i][j]) to[i].push_back(j); } } int ret = solve_by_flow_twice(to, x, y, z); cout << ret << '\n'; }