#include using namespace std; #include #include struct bimatch{ int n; vector >G; vectormatch; vectorused; bimatch(int _n=0):n(_n),G(n),match(n),used(n){} void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } bool dfs(int v) { used[v]=true; for(int u:G[v]) { int w=match[u]; if(w<0||!used[w]&&dfs(w)) { match[v]=u; match[u]=v; return true; } } return false; } int count() { int ans=0; bool flag=true; fill(match.begin(),match.end(),-1); while(flag) { flag=false; fill(used.begin(),used.end(),false); for(int v=0;v struct SCC{ int n; vectorcomp,order; vectorused; vector >G,RG; SCC(int _n=0):n(_n),comp(_n,-1),used(_n,false),G(_n),RG(_n){} void add_edge(int from,int to) { G[from].push_back(to); RG[to].push_back(from); } void copy(const vector >&H) { for(int i=0;i=0;i--)if(comp[order[i]]==-1)rdfs(order[i],cnt++); return cnt; } int build(vector >&H) { int ret=build(); H.assign(ret,vector()); for(int i=0;i>N>>M>>L; bimatch P(N+M); for(int i=0;i>U[i]>>V[i]; U[i]--,V[i]--; V[i]+=N; P.add_edge(U[i],V[i]); } P.count(); SCC Q(N+M+2); for(int i=0;i