#include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<std::ostream &operator<<(std::ostream&os,const std::pair&x){return os<<"("<std::ostream &operator<<(std::ostream&os,const std::vector&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<std::ostream &operator<<(std::ostream&os,const std::set&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<std::ostream&operator<<(std::ostream &os,const std::array &arr) {os<<'['<void print(std::ostream&os,const Tup &x,std::index_sequence){(void)(int[]){(os<(x)<<", ",0)...};} templatestd::ostream &operator<<(std::ostream&os,const std::tuple &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence());return os<(x)<<")";} const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m"; #define func_LINE_FILE NORMAL_FAINT<<" in "<"< blg[2]; std::vector> es; public: DulmageMendelsohn(int L, int R): blg{std::vector(L, -3), std::vector(R, -3)} {} void add_edge(int l, int r) { es.push_back({l, r}); } void build() { const int n[]= {blg[0].size(), blg[1].size()}; std::vector g[2], pos[2], rt, pre, mate[2], que(std::max(n[0], n[1])); g[0].resize(es.size()), g[1].resize(es.size()), pos[0].resize(n[0] + 1, 0), pos[1].resize(n[1] + 1, 0); mate[0].assign(n[0], -1), mate[1].assign(n[1], -1); for (auto [l, r]: es) ++pos[0][l], ++pos[1][r]; std::partial_sum(pos[0].begin(), pos[0].end(), pos[0].begin()), std::partial_sum(pos[1].begin(), pos[1].end(), pos[1].begin()); for (auto [l, r]: es) g[0][--pos[0][l]]= r, g[1][--pos[1][r]]= l; int t; for (bool upd= true; upd;) { upd= false, rt.assign(n[0], -1), pre.assign(n[0], -1), t= 0; for (int l= n[0]; l--;) if (mate[0][l] == -1) que[t++]= rt[l]= pre[l]= l; for (int i= 0; i < t; ++i) if (int l= que[i]; mate[0][rt[l]] == -1) for (int j= pos[0][l], r, nl; j < pos[0][l + 1]; ++j) { if (nl= mate[1][r= g[0][j]]; nl == -1) { for (upd= true; r != -1; l= pre[l]) mate[1][r]= l, std::swap(mate[0][l], r); break; } if (pre[nl] == -1) rt[que[t++]= nl]= rt[pre[nl]= l]; } } for (int l= n[0]; l--;) if (mate[0][l] == -1) blg[0][l]= -1; for (int r= n[1]; r--;) if (mate[1][r] == -1) blg[1][r]= -2; for (int s= n[0], i= t= 0; s--;) if (mate[0][s] == -1) for (que[t++]= s; i < t; ++i) for (int v= que[i], j= pos[0][v], u, w; j < pos[0][v + 1]; ++j) if (blg[1][u= g[0][j]] == -3) if (blg[1][u]= -1, w= mate[1][u]; w != -1 && blg[0][w] == -3) blg[0][que[t++]= w]= -1; for (int s= n[1], i= t= 0; s--;) if (mate[1][s] == -1) for (que[t++]= s; i < t; ++i) for (int v= que[i], j= pos[1][v], u, w; j < pos[1][v + 1]; ++j) if (blg[0][u= g[1][j]] == -3) if (blg[0][u]= -2, w= mate[0][u]; w != -1 && blg[1][w] == -3) blg[1][que[t++]= w]= -2; std::vector ei(pos[0].begin(), pos[0].begin() + n[0]); int oi= 0; for (int s= n[0], v; s--;) if (blg[0][s] == -3) for (blg[0][v= s]= n[0] * 2; v < n[0];) { if (ei[v] == pos[0][v + 1]) rt[oi++]= v, v= blg[0][v] - n[0]; else if (int u= g[0][ei[v]++]; blg[1][u] == -3) if (int w= mate[1][u]; blg[0][w] == -3) blg[0][w]= v + n[0], v= w; } int k= 0; for (int i= t= 0; oi--;) if (int s= rt[oi]; blg[0][s] >= n[0]) { int p= mate[0][s]; que[t++]= p, blg[0][s]= blg[1][p]= k; for (; i < t; ++i) { for (int v= que[i], j= pos[1][v], u, w; j < pos[1][v + 1]; ++j) { if (blg[0][u= g[1][j]] >= n[0]) { w= mate[0][u]; que[t++]= w, blg[0][u]= blg[1][w]= k; } } } ++k; } ++k; for (int l= n[0]; l--;) { if (blg[0][l] == -1) blg[0][l]= k; else if (blg[0][l] == -2) blg[0][l]= 0; else ++blg[0][l]; } for (int r= n[1]; r--;) { if (blg[1][r] == -1) blg[1][r]= k; else if (blg[1][r] == -2) blg[1][r]= 0; else ++blg[1][r]; } } int left_belong(int l) const { return blg[0][l]; } int right_belong(int r) const { return blg[1][r]; } }; using namespace std; namespace yukicoder1745 { signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, M, L; cin >> N >> M >> L; DulmageMendelsohn dm(N, M); int S[L], T[L]; for (int i= 0; i < L; ++i) { cin >> S[i] >> T[i]; dm.add_edge(--S[i], --T[i]); } dm.build(); for (int i= 0; i < L; ++i) { cout << (dm.left_belong(S[i]) == dm.right_belong(T[i]) ? "Yes" : "No") << '\n'; } return 0; } } signed main() { cin.tie(0); ios::sync_with_stdio(0); yukicoder1745::main(); return 0; }