#line 1 "sol.cpp" #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; template inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } template T ceil(T x, U y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x > 0 ? (x + y - 1) / y : x / y); } template T floor(T x, U y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x > 0 ? x / y : (x - y + 1) / y); } template int popcnt(T x) { return __builtin_popcountll(x); } template int topbit(T x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } template int 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]) { cout << "No" << '\n'; } else { cout << "Yes" << '\n'; } } return 0; }