#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" #include #include #include #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\csr-array.hpp" #include 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, 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]] = std::move(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 "D:\\Programming\\VSCode\\competitive-cpp\\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, int m = 0) : m_n(n), m_e(m), 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 static Graph Input(Cin& cin, int n, bool undirected, int m, bool offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } 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 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\strongly-connected-components.hpp" namespace nachia{ struct StronglyConnectedComponents{ private: int m_n; CsrArray induce; int componentNum; public: StronglyConnectedComponents() : m_n(0), induce(), componentNum(0) {} StronglyConnectedComponents(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 numComponents() const noexcept { return componentNum; } const CsrArray& getCsr() const noexcept { return induce; } std::vector getMapping() const { std::vector res(m_n); for(int i=0; i #include #line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\nyaanio.hpp" #include #include #include namespace fastio { static constexpr int SZ = 1 << 17; char inbuf[SZ], outbuf[SZ]; int in_left = 0, in_right = 0, out_right = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; inline void load() { int len = in_right - in_left; memmove(inbuf, inbuf + in_left, len); in_right = len + fread(inbuf + len, 1, SZ - len, stdin); in_left = 0; if(in_right != SZ) inbuf[in_right] = '\000'; } inline void flush() { fwrite(outbuf, 1, out_right, stdout); out_right = 0; } inline void skip_space() { if (in_left + 32 > in_right) load(); while (inbuf[in_left] <= ' ') in_left++; } inline void rd(char& c) { if (in_left + 32 > in_right) load(); c = inbuf[in_left++]; } template inline void rd(T& x) { if (in_left + (int)sizeof(T) * 8 > in_right) load(); char c; do c = inbuf[in_left++]; while (c < '-'); [[maybe_unused]] bool minus = false; if constexpr (std::is_signed::value == true) { if (c == '-') minus = true, c = inbuf[in_left++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = inbuf[in_left++]; } if constexpr (std::is_signed::value == true) { if (minus) x = -x; } } inline void wt(char c) { if (out_right > SZ - 32) flush(); outbuf[out_right++] = c; } inline void wt(bool b) { if (out_right > SZ - 32) flush(); outbuf[out_right++] = b ? '1' : '0'; } inline void wt(const std::string &s) { if (out_right + s.size() > SZ - 32) flush(); if (s.size() > SZ - 32){ fwrite(s.c_str(), 1, s.size(), stdout); return; } memcpy(outbuf + out_right, s.data(), sizeof(char) * s.size()); out_right += s.size(); } inline void wt(const char* s) { wt(std::string(s)); } template inline void wt(T x) { if (out_right > SZ - (int)sizeof(T) * 8) flush(); if (!x) { outbuf[out_right++] = '0'; return; } if constexpr (std::is_signed::value == true) { if (x < 0) outbuf[out_right++] = '-', x = -x; } constexpr int SZT = sizeof(T) * 8; int i = SZT - 4; char buf[SZT]; while (x >= 10000) { memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; i -= 4; } if (x < 100) { if (x < 10) { outbuf[out_right] = '0' + x; ++out_right; } else { uint32_t q = (uint32_t(x) * 205) >> 11; uint32_t r = uint32_t(x) - q * 10; outbuf[out_right] = '0' + q; outbuf[out_right + 1] = '0' + r; out_right += 2; } } else { if (x < 1000) { memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3); out_right += 3; } else { memcpy(outbuf + out_right, pre.num + (x << 2), 4); out_right += 4; } } memcpy(outbuf + out_right, buf + i + 4, SZT - 4 - i); out_right += SZT - 4 - i; } } // namespace fastio namespace nachia{ struct CInStream{} cin; template inline CInStream& operator>>(CInStream& c, T& dest){ fastio::rd(dest); return c; } struct COutStream{ ~COutStream(){ atexit(fastio::flush); } } cout; template inline COutStream& operator<<(COutStream& c, const T& src){ fastio::wt(src); return c; } } // namespace nachia #line 3 "..\\Main.cpp" int main(){ using nachia::cin; using nachia::cout; 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::StronglyConnectedComponents(graph).getCsr(); std::vector sccid(N); for(int i=0; i nxV(N, -1); for(auto e : graph2){ if(nxV[e.from] == -1) nxV[e.from] = e.to; else nxV[e.from] = -2; } int N4 = 0; std::vector skippedV(N, -1); for(int i=0; i partAns(N4-1, 1); for(auto e : graph2){ int u = skippedV[e.from]; if(u == -1) continue; int p = e.to; int w = 1; while(nxV[p] >= 0){ p = nxV[p]; w++; } int v = skippedV[p]; for(int i=u; i