#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include // #include // #include // #include // using namespace __gnu_pbds; // #include // namespace multiprecisioninteger = boost::multiprecision; // using cint=multiprecisioninteger::cpp_int; using namespace std; using ll=long long; using datas=pair; using ddatas=pair; using tdata=pair; using vec=vector; using mat=vector; using pvec=vector; using pmat=vector; // using llset=tree,rb_tree_tag,tree_order_statistics_node_update>; #define For(i,a,b) for(i=a;i<(ll)b;++i) #define bFor(i,b,a) for(i=b,--i;i>=(ll)a;--i) #define rep(i,N) For(i,0,N) #define rep1(i,N) For(i,1,N) #define brep(i,N) bFor(i,N,0) #define brep1(i,N) bFor(i,N,1) #define all(v) (v).begin(),(v).end() #define allr(v) (v).rbegin(),(v).rend() #define vsort(v) sort(all(v)) #define vrsort(v) sort(allr(v)) #define uniq(v) vsort(v),(v).erase(unique(all(v)),(v).end()) #define endl "\n" #define popcount __builtin_popcountll #define eb emplace_back #define print(x) cout< ostream& operator<<(ostream& os,const pair& p){return os<<"("< ostream& operator<<(ostream& os,const vector& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const set& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const multiset& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const map& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< inline bool chmax(T& a,const T b){bool x=a inline bool chmin(T& a,const T b){bool x=a>b;if(x)a=b;return x;} #ifdef DEBUG void debugg(){cout<void debugg(const T& x,const Args&... args){cout<<" "<> g):_n(g.size()){ for(int i=0;i<_n;++i)for(auto& x:g[i])add_edge(i,x); scc_ids(); } scc_graph(vector> g):_n(g.size()){ for(int i=0;i<_n;++i)for(auto& x:g[i])add_edge(i,x); scc_ids(); } void add_edge(int from,int to){ assert(0<=from&&from<_n); assert(0<=to&&to<_n); edges.push_back({from,{to}}); } void add_clause(int i,bool f,int j,bool g){ assert(0<=i&&i*2<_n); assert(0<=j&&j*2<_n); add_edge(i<<1|!f,j<<1|g); add_edge(j<<1|!g,i<<1|f); } //n must be *2 vector solve_twosat(){ if(!group_num)scc_ids(); int m=_n>>1; vector answer(m); for(int i=0;i> scc(){ if(!group_num)scc_ids(); vector counts(group_num); for(auto& x:ids)counts[x]++; vector> groups(group_num); for(int i=0;i start; vector elist; csr(int n,const vector>& edges):start(n+1),elist(edges.size()){ for(auto& e:edges)++start[e.first+1]; for(int i=0;i ids; vector> edges; // @return pair of(# of scc,scc id) void scc_ids(){ auto g=csr(_n,edges); int now_ord=0; vector visited,low(_n),ord(_n,-1); ids.resize(_n); visited.reserve(_n); auto dfs=[&](auto self,int v)-> void{ low[v]=ord[v]=now_ord++; visited.push_back(v); for(int i=g.start[v];i int N,M,L; int main(){ startupcpp(); ll i,j; cin>>N>>M>>L; atcoder::mf_graph g(N+M+2); rep(i,N)g.add_edge(N+M,i,1); rep(i,M)g.add_edge(i+N,N+M+1,1); rep(i,L){ int S,T; cin>>S>>T; --S;--T; g.add_edge(S,T+N,1); } g.flow(N+M,N+M+1); scc_graph sg(N+M+2),tg(N+M+2),chg(N+M); mat gs(N+M+2),gt(N+M+2); for(auto edge:g.edges()){ int s=edge.from,t=edge.to; if(edge.flow){ tg.add_edge(s,t); gt[s].emplace_back(t); sg.add_edge(t,s); gs[t].emplace_back(s); }else{ sg.add_edge(s,t); gs[s].emplace_back(t); tg.add_edge(t,s); gt[t].emplace_back(s); } if(max(s,t)>=N+M)continue; if(edge.flow)chg.add_edge(s,t); else chg.add_edge(t,s); } auto sgscc=sg.scc(); auto tgscc=tg.scc(); chg.scc(); vector vissg(sgscc.size(),0); vissg[sg[N+M]]=true; rep(i,sgscc.size()){ if(!vissg[i])continue; for(auto s:sgscc[i]){ for(auto t:gs[s])vissg[sg[t]]=true; } } vector vistg(tgscc.size(),0); vistg[tg[N+M+1]]=true; rep(i,tgscc.size()){ if(!vistg[i])continue; for(auto t:tgscc[i]){ for(auto s:gt[t])vistg[tg[s]]=true; } } rep(i,L){ auto edge=g.get_edge(N+M+i); if(edge.flow||vissg[sg[edge.from]]||vistg[tg[edge.to]]||chg[edge.from]==chg[edge.to])printyes; else printno; } }