#include using namespace std; pair, vector > BipartiteMatching(int L, int R, const vector > &e) { vector > g(L); for(auto [a,b] : e) g[a].push_back(b); vector matL(L, -1), matR(R, -1); vector vis(L); auto DFS = [&](auto &self, int n)->bool { if (vis[n]) return false; vis[n] = true; for(int next : g[n]) if (matR[next] == -1) { matL[n] = next, matR[next] = n; return true; } for(int next : g[n]) if (self(self, matR[next])) { matL[n] = next, matR[next] = n; return true; } return false; }; for(int i=0; i > StronglyConnectedComponents(int N, const vector > &e) { vector > g(N), rg(N); for(auto [a,b] : e) g[a].push_back(b), rg[b].push_back(a); vector vis(N); vector stk; auto DFS = [&](auto &self, int n)->void { vis[n] = true; for(int next : g[n]) if (!vis[next]) self(self, next); stk.push_back(n); }; for(int n=0; n myscc(N); auto DFS2 = [&](auto &self, int n)->void { vis[n] = true; for(int next : rg[n]) if (!vis[next]) self(self, next); myscc[n] = SCC; }; fill(vis.begin(), vis.end(), false); while(!stk.empty()) { int n = stk.back(); stk.pop_back(); if (vis[n]) continue; DFS2(DFS2, n); SCC++; } return {SCC, myscc}; } vector, vector > > DulmageMendelsohn(int L, int R, const vector > &e) { auto [matL, matR] = BipartiteMatching(L, R, e); vector mat(L+R); for(int i=0; i > g(L+R); for(auto [a,b] : e) { g[a].push_back(L+b); g[L+b].push_back(a); } vector col(L+R, -1); // (-1, 0, 1) = (U, E, O) auto DFS = [&](auto &self, int n)->void { col[n] = 0; for(int next : g[n]) { col[next] = 1; if (col[mat[next]] == -1) self(self, mat[next]); } }; for(int i=0; i > E; // directed edges for(auto [a,b] : e) if (col[a] == -1 && col[L+b] == -1) E.push_back({a, L+b}); for(int i=0; i, vector > > ret(K+2); for(int i=0; i> N >> M >> L; vector > e; for(int i=0; i> a >> b; a--; b--; // 0-based e.push_back({a, b}); } auto v = DulmageMendelsohn(N, M, e); vector pos(N+M); for(int i=0; i