#include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin()) #define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin()) using ll=long long int; using ull=unsigned long long; using i128=__int128_t; using u128=__uint128_t; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} templateT ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);} templateT floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);} templateint popcnt(T x){return __builtin_popcountll(x);} templateint topbit(T x){return (x==0?-1:63-__builtin_clzll(x));} templateint lowbit(T x){return (x==0?-1:__builtin_ctzll(x));} vector BiMatching(int n,int m,vector>& g){ vector L(n,-1),R(m,-1); for(;;){ vector par(n,-1),root(n,-1); queue que; rep(i,0,n)if(L[i]==-1){ que.push(i); root[i]=i; } bool upd=0; while(!que.empty()){ int v=que.front(); que.pop(); if(L[root[v]]!=-1)continue; for(auto u:g[v]){ if(R[u]==-1){ while(u!=-1){ R[u]=v; swap(L[v],u); v=par[v]; } upd=1; break; } int to=R[u]; if(par[to]==-1){ root[to]=root[v]; par[to]=v; que.push(to); } } } if(!upd)break; } return L; } struct SCC{ int n,m,cur; vector> g; vector low,ord,id; SCC(int _n=0):n(_n),m(0),cur(0),g(_n),low(_n),ord(_n,-1),id(_n){} void resize(int _n){ n=_n; g.resize(n); low.resize(n); ord.resize(n,-1); id.resize(n); } void add_edge(int u,int v){g[u].emplace_back(v);} void dfs(int v,vector& used){ ord[v]=low[v]=cur++; used.emplace_back(v); for(auto& nxt:g[v]){ if(ord[nxt]==-1){ dfs(nxt,used); chmin(low[v],low[nxt]); } else{ chmin(low[v],ord[nxt]); } } if(ord[v]==low[v]){ while(1){ int add=used.back(); used.pop_back(); ord[add]=n; id[add]=m; if(v==add)break; } m++; } } void run(){ vector used; rep(v,0,n)if(ord[v]==-1)dfs(v,used); for(auto& x:id)x=m-1-x; } }; #define debug(var) do{std::cerr << #var << " : ";view(var);}while(0) template void view(T e){std::cerr << e << std::endl;} template void view(const std::vector& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;} template void view(const std::vector >& vv){ for(const auto& v : vv){ view(v); } } vector> DMdecomposition(int n,int m,vector>& g){ auto L=BiMatching(n,m,g); vector G(n+m,vector()),REV(n+m,vector()); rep(i,0,n)for(auto& j:g[i]){ G[i].push_back(j+n); REV[j+n].push_back(i); } vector R(m,-1); rep(i,0,n)if(L[i]!=-1){ G[L[i]+n].push_back(i); REV[i].push_back(L[i]+n); R[L[i]]=i; } vector V0,Vinf; queue que; vector used(n+m); rep(i,0,n)if(L[i]==-1){ used[i]=1; que.push(i); } while(!que.empty()){ int v=que.front(); que.pop(); Vinf.push_back(v); for(auto& to:G[v])if(!used[to]){ used[to]=1; que.push(to); } } rep(i,0,m)if(R[i]==-1){ used[i+n]=1; que.push(i+n); } while(!que.empty()){ int v=que.front(); que.pop(); V0.push_back(v); for(auto& to:REV[v])if(!used[to]){ used[to]=1; que.push(to); } } SCC scc(n+m); rep(i,0,n+m)for(auto& to:G[i]){ if(!used[i] and !used[to])scc.add_edge(i,to); } scc.run(); vector group(scc.m,vector()); rep(i,0,n+m)if(!used[i])group[scc.id[i]].push_back(i); vector> ret; ret.push_back(V0); for(auto& v:group)ret.push_back(v); ret.push_back(Vinf); return ret; } int main(){ int n,m,L; cin>>n>>m>>L; vector> g(n); vector u(L),v(L); rep(i,0,L){ cin>>u[i]>>v[i]; u[i]--; v[i]--; g[u[i]].push_back(v[i]); } auto ret=DMdecomposition(n,m,g); vector ord(n+m,-1); rep(i,0,SZ(ret))for(auto& v:ret[i])ord[v]=i; // debug(ret); rep(i,0,L){ if(ord[u[i]]==ord[v[i]+n] and ord[u[i]]!=0 and ord[u[i]]!=SZ(ret)-1 and SZ(ret[ord[u[i]]])<=2){ cout<<"No"<<'\n'; } else{ cout<<"Yes"<<'\n'; } } return 0; }