#line 1 "Main.cpp" #include #include #include #include #include #line 4 "nachia\\graph\\graph.hpp" #include #line 5 "nachia\\array\\csr-array.hpp" namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, const std::vector>& items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = items[i].second; } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 6 "nachia\\graph\\graph.hpp" namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } }; using Base = std::vector>; Graph(int n = 0, bool undirected = false) : m_n(n), m_e(), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {} Graph(int n, std::vector&& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {} int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = ++newV[mapping[i]]; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia #line 4 "nachia\\graph\\strongly-connected-components.hpp" namespace nachia{ struct SCC{ int m_n; CsrArray induce; int componentNum; SCC() : m_n(0), induce(), componentNum(0) {} SCC(Graph E) { int n = E.numVertices(); m_n = n; std::vector O(n); { auto adj = E.getAdjacencyArray(); int Oi = n; std::vector P(n, -1), EI(n, 0); for(int s=0; s= 0){ if(EI[p] == adj[p].size()){ O[--Oi] = p; p = P[p]; continue; } int q = adj[p][EI[p]++]; if(P[q] == -1){ P[q] = p; p = q; } } } } E.reverseEdges(); auto adj = E.getAdjacencyArray(); std::vector sep = {0}, csr(n), vis(n,0); int p1 = 0, p2 = 0; for(int s : O) if(!vis[s]){ csr[p2++] = s; vis[s] = 1; for(; p1::FromRaw(std::move(csr), std::move(sep)); componentNum = induce.size(); } int numComponent() const { return componentNum; } const CsrArray& getCsr() const { return induce; } }; } // namespace nachia #line 7 "Main.cpp" using namespace std; using i64 = long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // グラフの入力・整形 int N1, N2, N3, M; cin >> N1 >> N2 >> N3 >> M; int s = N1+N2+N3, t = N1+N2+N3+1, N = N1+N2+N3+2; nachia::Graph graph(N, false); if(N1 != 0){ graph.addEdge(s, 0); for(int i=0; i> u >> v; u--; v--; graph.addEdge(u, v); graph.addEdge(v, u); } // 強連結成分分解 auto scc = nachia::SCC(graph).getCsr(); vector sccid(N); rep(i,scc.size()) for(int j : scc[i]) sccid[j] = i; // 強連結成分の縮約 N = scc.size(); s = sccid[s]; t = sccid[t]; if(s == t){ cout << "0\n"; return 0; } nachia::Graph graph2(N, false); for(auto e : graph) if(sccid[e.from] != sccid[e.to]) graph2.addEdge(sccid[e.from], sccid[e.to]); // 次数 1,1 の頂点を検出 vector SkipV(N, 0); auto adj_graph2u = graph2.getAdjacencyArray(true); rep(i,N) if(adj_graph2u[i].size() == 2) SkipV[i] = -1; int N4 = 0; for(int& i : SkipV) if(i != -1) i = N4++; // 次数 1,1 の頂点を飛ばしたグラフを作成 nachia::Graph graph3(N4, false); std::vector W; auto adj_graph2d = graph2.getAdjacencyArray(false); rep(v, N) if(SkipV[v] != -1) for(int w : adj_graph2d[v]){ int weight = 1; while(SkipV[w] == -1){ w = adj_graph2d[w][0]; weight++; } graph3.addEdge(SkipV[v], SkipV[w]); W.push_back(weight); } // 数え上げ std::vector partAns(N4-1, 1); rep(e,graph3.numEdges()) for(int i=graph3[e].from; i