#include using namespace std; #include using namespace atcoder; #define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) // rep(i, a): [0, a); rep(i, a, b): [a, b) struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; template istream &operator>>(istream &is, vector &v) { for (auto &e : v) is >> e; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (auto &e : v) os << e << ' '; return os; } #ifdef LOCAL void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif struct dm_decomposition { using edge = pair; int r, c; vector E; dm_decomposition(int _r, int _c) : r(_r), c(_c) {} void add_edge(int i, int j) { E.emplace_back(i, j); } pair>, vector>> decompose() { int n = r + c, m = E.size(); int s = n, t = s + 1; vector>> G(n); vector is_used_V(n); { // max flow atcoder::mf_graph mfg(n + 2); for (auto [i, j] : E) mfg.add_edge(i, r + j, 1); for (int i = 0; i < r; i++) mfg.add_edge(s, i, 1); for (int j = 0; j < c; j++) mfg.add_edge(r + j, t, 1); mfg.flow(s, t); // construct graph for (int k = 0; k < m; k++) { auto e = mfg.get_edge(k); if (e.flow == 1) { G[e.from].push_back({k, e.to, 3}); G[e.to].push_back({k, e.from, 3}); is_used_V[e.from] = is_used_V[e.to] = true; } else { G[e.from].push_back({k, e.to, 1}); G[e.to].push_back({k, e.from, 2}); } } } vector V_0, V_inf; { // check reachability vector R_unused, C_unused; for (int u = 0; u < r; u++) if (!is_used_V[u]) R_unused.push_back(u); for (int u = r; u < n; u++) if (!is_used_V[u]) C_unused.push_back(u); auto bfs = [&] (vector& S, bool fwd) { vector seen(n); queue que; for (auto u : S) seen[u] = true, que.push(u); while (!que.empty()) { auto u = que.front(); que.pop(); for (auto [id, v, d] : G[u]) { if ((fwd && (d >> 0 & 1)) || (!fwd && (d >> 1 & 1))) { if (seen[v] == false) seen[v] = true, que.push(v); } } } vector res; for (int u = 0; u < n; u++) if (seen[u]) res.push_back(u); return res; }; V_inf = bfs(R_unused, true); V_0 = bfs(C_unused, false); } // erase nodes and edges vector is_erased_V(n), is_erased_E(m); for (auto u : V_0) { is_erased_V[u] = true; for (auto [id, v, d] : G[u]) is_erased_E[id] = true; } for (auto u : V_inf) { is_erased_V[u] = true; for (auto [id, v, d] : G[u]) is_erased_E[id] = true; } vector> Rs, Cs; auto push_nodes = [&] (vector& V) { if (V.empty()) return; Rs.push_back({}), Cs.push_back({}); for (auto u : V) { if (u < r) Rs.back().push_back(u); else Cs.back().push_back(u - r); } }; push_nodes(V_0); // scc decomposition atcoder::scc_graph sccg(n); for (int u = 0; u < n; u++) { for (auto [id, v, d] : G[u]) { if ((d & 1) && !is_erased_E[id]) sccg.add_edge(u, v); } } for (auto vs : sccg.scc()) { if (is_erased_V[vs.front()]) continue; push_nodes(vs); } push_nodes(V_inf); return {Rs, Cs}; } }; void solve() { int n, m, l; cin >> n >> m >> l; assert(1 <= n && n <= 1000); assert(1 <= m && m <= 1000); assert(1 <= l && l <= int(1e5)); dm_decomposition dm(n, m); set> S; rep(i, l) { int s, t; cin >> s >> t; assert(1 <= s && s <= n); assert(1 <= t && t <= m); S.emplace(s, t); --s, --t; dm.add_edge(s, t); } assert(S.size() == l); auto [rs, cs] = dm.decompose(); vector cid_R(n), cid_C(m); int cnum = rs.size(); rep(k, cnum) for (auto i : rs[k]) cid_R[i] = k; rep(k, cnum) for (auto i : cs[k]) cid_C[i] = k; for (auto [i, j] : dm.E) { bool ans = true; int p = cid_R[i], q = cid_C[j]; if (p == q && rs[p].size() == 1 && cs[q].size() == 1) ans = false; cout << (ans ? "Yes" : "No") << '\n'; } } int main() { solve(); }