#include using namespace std; #define ll long long #define rep(i,n) for(int i=0;i=0;i--) #define rrep2(i,n,k) for(int i=n-1;i>=n-k;i--) #define vll(n,i) vector(n,i) #define v2ll(n,m,i) vector>(n,vll(m,i)) #define v3ll(n,m,k,i) vector>>(n,v2ll(m,k,i)) #define v4ll(n,m,k,l,i) vector>>>(n,v3ll(m,k,l,i)) #define all(v) v.begin(),v.end() #define chmin(k,m) k = min(k,m) #define chmax(k,m) k = max(k,m) #define Pr pair #define Tp tuple #define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr) using Graph = vector>; const ll mod = 998244353; template struct modint{ uint64_t val; constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){} constexpr modint operator-() const noexcept{ return modint(*this)=mod-val; } constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint &operator+=(const modint rhs) noexcept{ val+=rhs.val; val-=((val>=mod)?mod:0); return (*this); } constexpr modint &operator-=(const modint rhs) noexcept{ val+=((val>=1; } return (*this)*=now; } modint & operator++(){ val++; if (val == mod) val = 0; return *this; } modint operator++(int){ modint res = *this; ++*this; return res; } constexpr bool operator==(const modint rhs) noexcept{ return val==rhs.val; } constexpr bool operator!=(const modint rhs) noexcept{ return val!=rhs.val; } friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{ return os<<(x.val); } friend constexpr istream &operator>>(istream& is,modint& x) noexcept{ uint64_t t; is>>t,x=t; return is; } }; typedef modint mint; #define vm(n,i) vector(n,i) #define v2m(n,m,i) vector>(n,vm(m,i)) #define v3m(n,m,k,i) vector>>(n,v2m(m,k,i)) #define v4m(n,m,k,l,i) vector>>>(n,v3m(m,k,l,i)) //ration operation stack //作成中 struct range_operaion_stack { vector> range; range_operaion_stack(ll start,ll size,ll inf) { range.push_back(make_tuple(inf,start,start)); } ll add(ll i,ll x){ int n = range.size() -1; ll k = get<0>(range[n]); ll i1 = i; while(k>=x){ //右からの区間最小値更新の場合(最大値は-1倍して使う) ll j1 = get<1>(range[n]); ll j2 = get<2>(range[n]); i1 = j1; range.pop_back(); n = range.size() -1; k = get<0>(range[n]); } range.push_back(make_tuple(x,i1,i)); return i1; } //s以上の区間の端を返す ll id(ll s){ ll k = lower_bound(all(range),make_tuple(s,-1,-1))-range.begin(); if(k==range.size()) return -1; return get<1>(range[k]); } }; //Dinic template< typename flow_t > struct Dinic { const flow_t INF; struct edge { int to; flow_t cap; int rev; bool isrev; int idx; }; vector< vector< edge > > graph; vector< int > min_cost, iter; Dinic(int V) : INF(numeric_limits< flow_t >::max()), graph(V) {} void add_edge(int from, int to, flow_t cap, int idx = -1) { graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx}); graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx}); } bool bfs(int s, int t) { min_cost.assign(graph.size(), -1); queue< int > que; min_cost[s] = 0; que.push(s); while(!que.empty() && min_cost[t] == -1) { int p = que.front(); que.pop(); for(auto &e : graph[p]) { if(e.cap > 0 && min_cost[e.to] == -1) { min_cost[e.to] = min_cost[p] + 1; que.push(e.to); } } } return min_cost[t] != -1; } flow_t dfs(int idx, const int t, flow_t flow) { if(idx == t) return flow; for(int &i = iter[idx]; i < graph[idx].size(); i++) { edge &e = graph[idx][i]; if(e.cap > 0 && min_cost[idx] < min_cost[e.to]) { flow_t d = dfs(e.to, t, min(flow, e.cap)); if(d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } flow_t max_flow(int s, int t) { flow_t flow = 0; while(bfs(s, t)) { iter.assign(graph.size(), 0); flow_t f = 0; while((f = dfs(s, t, INF)) > 0) flow += f; } return flow; } vector output(ll N) { vector v; for(int i = 0; i < graph.size(); i++) { for(auto &e : graph[i]) { if(e.isrev) continue; auto &rev_e = graph[e.to][e.rev]; if(i!=0&&i<=N&&rev_e.cap>0){ v.push_back(make_pair(i,e.to)); } //cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl; } } return v; } }; //SCC 各頂点にSCC順の番号を格納して返す void dfs_scc(Graph &G,vector &perm_back,vector &vis,long long i,int j){ vis[i] = true; for(long long x:G[i]){ if(vis[x]) continue; dfs_scc(G,perm_back,vis,x,j); } if(j==-1) perm_back.push_back(i); else perm_back[i] = j; } vector scc(Graph &G){ int N = G.size(); vector perm_back; vector vis(N,false); for(int i=0;i scc_label(N); vis.assign(N,false); for(int i=0;i> N >> M >> L; //main関数内 Dinic G(N+M+2); Graph G2(N+M+2); vector ed; map lab; rep(i,L){ ll s,t; cin >> s >> t; G.add_edge(s,N+t,1); ed.push_back(make_pair(s,N+t)); lab[make_pair(s,t+N)] = i; } rep(i,N){ G.add_edge(0,i+1,1); } rep(i,M){ G.add_edge(N+i+1,N+M+1,1); } G.max_flow(0,N+M+1); auto v = G.output(N); // for(auto[x,y]:v){ // cout << x << " " << y << endl; // } bool rev[L]; rep(i,L) rev[i] = true; for(Pr p:v){ rev[lab[p]] = false; } auto in = vll(N+M+1,0); rep(i,L){ if(rev[i]){ auto[s,t] = ed[i]; G2[t].push_back(s); in[s]++; } else{ auto[s,t] = ed[i]; G2[s].push_back(t); in[t]++; } } //BFS (普通の幅優先探索) queue go; ll dist[N+M+1]; // ll par[N+1]; rep(i,N+M+1){ dist[i] = 2000000000; } for(int i=N+1;i<=N+M;i++){ if(in[i]==0){ go.push(i); } } while(!go.empty()){ int s = go.front(); go.pop(); for(int x:G2[s]){ if(dist[x]<=dist[s]+1) continue; if(s<=N){ rev[lab[make_pair(s,x)]] = true; } dist[x] = dist[s] + 1; go.push(x); } } //main関数内 auto v2 = scc(G2); rep(i,L){ if(rev[i]){ cout << "Yes" << "\n"; } else{ auto[s,t] = ed[i]; if(v2[s]==v2[t]) cout << "Yes" << "\n"; else cout << "No" << "\n"; } } }