#line 1 "Contests/yukicoder_/6654/main.cpp" /* #define aclmodint */ /* #define aclsegtree */ /* #include */ /* using namespace atcoder; */ #line 1 "library/atcoder/maxflow.hpp" #include #include #include #include #include #line 1 "library/atcoder/internal_queue.hpp" #line 5 "library/atcoder/internal_queue.hpp" namespace atcoder { namespace internal { template struct simple_queue { std::vector payload; int pos = 0; void reserve(int n) { payload.reserve(n); } int size() const { return int(payload.size()) - pos; } bool empty() const { return pos == int(payload.size()); } void push(const T& t) { payload.push_back(t); } T& front() { return payload[pos]; } void clear() { payload.clear(); pos = 0; } void pop() { pos++; } }; } // namespace internal } // namespace atcoder #line 11 "library/atcoder/maxflow.hpp" namespace atcoder { template struct mf_graph { public: mf_graph() : _n(0) {} explicit mf_graph(int n) : _n(n), g(n) {} int add_edge(int from, int to, Cap cap) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); int m = int(pos.size()); pos.push_back({from, int(g[from].size())}); int from_id = int(g[from].size()); int to_id = int(g[to].size()); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = int(pos.size()); assert(0 <= i && i < m); auto _e = g[pos[i].first][pos[i].second]; auto _re = g[_e.to][_e.rev]; return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap}; } std::vector edges() { int m = int(pos.size()); std::vector result; for (int i = 0; i < m; i++) { result.push_back(get_edge(i)); } return result; } void change_edge(int i, Cap new_cap, Cap new_flow) { int m = int(pos.size()); assert(0 <= i && i < m); assert(0 <= new_flow && new_flow <= new_cap); auto& _e = g[pos[i].first][pos[i].second]; auto& _re = g[_e.to][_e.rev]; _e.cap = new_cap - new_flow; _re.cap = new_flow; } Cap flow(int s, int t) { return flow(s, t, std::numeric_limits::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); std::vector level(_n), iter(_n); internal::simple_queue que; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto e : g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; Cap res = 0; int level_v = level[v]; for (int& i = iter[v]; i < int(g[v].size()); i++) { _edge& e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) return res; } level[v] = _n; return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); if (level[t] == -1) break; std::fill(iter.begin(), iter.end(), 0); Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } return flow; } std::vector min_cut(int s) { std::vector visited(_n); internal::simple_queue que; que.push(s); while (!que.empty()) { int p = que.front(); que.pop(); visited[p] = true; for (auto e : g[p]) { if (e.cap && !visited[e.to]) { visited[e.to] = true; que.push(e.to); } } } return visited; } private: int _n; struct _edge { int to, rev; Cap cap; }; std::vector> pos; std::vector> g; }; } // namespace atcoder #line 1 "library/atcoder/dsu.hpp" #line 7 "library/atcoder/dsu.hpp" namespace atcoder { // Implement (union by size) + (path compression) // Reference: // Zvi Galil and Giuseppe F. Italiano, // Data structures and algorithms for disjoint set union problems struct dsu { public: dsu() : _n(0) {} explicit dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; }; } // namespace atcoder #line 8 "Contests/yukicoder_/6654/main.cpp" using namespace atcoder; #line 1 "library/me/template.cpp" #include using namespace std; #define REP(a,b) for(int a = 0;a < (int)(b);++a) #define FOR(i,a,b) for(ll i = a; i < (ll)(b); i++) #define ALL(a) (a).begin(),(a).end() #define END(a) { print(a); return; } #define DBG(a) { cerr << #a << ": "; dbg(a); } using VI = vector; using VVI = vector; using VVVI = vector; using ll = long long; using VL = vector; using VVL = vector; using VVVL = vector; using VD = vector; using VVD = vector; using VVVD = vector; using VS = vector; using VVS = vector; using VVVS = vector; using VC = vector; using VVC = vector; using VVVC = vector; using P = pair; using VP = vector

; using VVP = vector; using VVVP = vector; using LP = pair; using VLP = vector; using VVLP = vector; using VVVLP = vector; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; #ifdef aclmodint using MI7 = modint1000000007; using V7 = vector; using VV7 = vector; using VVV7 = vector; using MI3 = modint998244353; using V3 = vector; using VV3 = vector; using VVV3 = vector; ostream &operator<<(ostream &os, const modint &x) { os << x.val(); return os; } ostream &operator<<(ostream &os, const MI3 &x) { os << x.val(); return os; } ostream &operator<<(ostream &os, const MI7 &x) { os << x.val(); return os; } istream &operator>>(istream &is, modint &x) { int y; is >> y; x = y; return is; } istream &operator>>(istream &is, MI3 &x) { int y; is >> y; x = y; return is; } istream &operator>>(istream &is, MI7 &x) { int y; is >> y; x = y; return is; } #endif void print() { cout << '\n'; } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } void dbg() { cout << '\n'; } template void dbg(const T &t) { cerr << t << '\n'; } template void dbg(const Head &head, const Tail &... tail) { cerr << head << ' '; dbg(tail...); } template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template pair> compress(const vector &a) { int n = a.size(); vector x; REP(i, n) x.push_back(i); sort(ALL(x)); x.erase(unique(ALL(x)), x.end()); VI res(n); REP(i, n) res[i] = lower_bound(ALL(x), a); return make_pair(res, x); } #ifdef aclsegtree template struct value_size { S value; int size; }; template S min_op(S l, S r) { return min(l, r); }; template S max_op(S l, S r) { return max(l, r); }; template S sum_op(S l, S r) { return l + r; }; template value_size sum_op_size(value_size l, value_size r) { return {l.value + r.value, l.size + r.size}; }; template value_size min_op_size(value_size l, value_size r) { return {min(l.value, r.value), l.size + r.size}; }; template value_size max_op_size(value_size l, value_size r) { return {max(l.value, r.value), l.size + r.size}; }; template S min_e() { return numeric_limits::max(); }; template S max_e() { return numeric_limits::min(); }; template S sum_e() { return 0; } template value_size sum_e_size() { return {0, 0}; } template value_size min_e_size() { return {numeric_limits::max(), 0}; } template value_size max_e_size() { return {numeric_limits::min(), 0}; } template S chmin_mapping(F f, S x) { return min(x, f); } template S chmax_mapping(F f, S x) { return max(x, f); } template S add_mapping(F f, S x) { return x + f; } template value_size add_mapping_size(F f, value_size x) { return {x.value + x.size * f, x.size}; } template F chmin_composition(F f, F g) { return min(f, g); } template F chmax_composition(F f, F g) { return max(f, g); } template F add_composition(F f, F g) { return f + g; } template F chmin_id() { return numeric_limits::max(); } template F chmax_id() { return numeric_limits::min(); } template F add_id() { return 0; } template using RSumQ = segtree, sum_e>; template using RMaxQ = segtree, max_e>; template using RMinQ = segtree, min_e>; template using RAddSumQ = lazy_segtree, sum_op_size, sum_e_size, F, add_mapping_size, add_composition, add_id>; template using RAddMinQ = lazy_segtree, min_e, F, add_mapping, add_composition, add_id>; template using RAddMaxQ = lazy_segtree, max_e, F, add_mapping, add_composition, add_id>; template using RMinMinQ = lazy_segtree, min_e, F, chmin_mapping, chmin_composition, chmin_id>; template using RMaxMaxQ = lazy_segtree, max_e, F, chmax_mapping, chmax_composition, chmax_id>; #endif #line 2 "library/ei1333/graph/connected-components/strongly-connected-components.hpp" #line 2 "library/ei1333/graph/graph-template.hpp" /** * @brief Graph Template(グラフテンプレート) */ template< typename T = int > struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template< typename T = int > struct Graph { vector< vector< Edge< T > > > g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) { for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if(weighted) cin >> c; if(directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } inline vector< Edge< T > > &operator[](const int &k) { return g[k]; } inline const vector< Edge< T > > &operator[](const int &k) const { return g[k]; } }; template< typename T = int > using Edges = vector< Edge< T > >; #line 4 "library/ei1333/graph/connected-components/strongly-connected-components.hpp" /** * @brief Strongly Connected Components(強連結成分分解) * @docs docs/strongly-connected-components.md */ template< typename T = int > struct StronglyConnectedComponents : Graph< T > { public: using Graph< T >::Graph; using Graph< T >::g; vector< int > comp; Graph< T > dag; vector< vector< int > > group; void build() { rg = Graph< T >(g.size()); for(size_t i = 0; i < g.size(); i++) { for(auto &e : g[i]) { rg.add_directed_edge(e.to, e.from, e.cost); } } comp.assign(g.size(), -1); used.assign(g.size(), 0); for(size_t i = 0; i < g.size(); i++) dfs(i); reverse(begin(order), end(order)); int ptr = 0; for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++; dag = Graph< T >(ptr); for(size_t i = 0; i < g.size(); i++) { for(auto &e : g[i]) { int x = comp[e.from], y = comp[e.to]; if(x == y) continue; dag.add_directed_edge(x, y, e.cost); } } group.resize(ptr); for(size_t i = 0; i < g.size(); i++) { group[comp[i]].emplace_back(i); } } int operator[](int k) const { return comp[k]; } private: vector< int > order, used; Graph< T > rg; void dfs(int idx) { if(exchange(used[idx], true)) return; for(auto &to : g[idx]) dfs(to); order.push_back(idx); } void rdfs(int idx, int cnt) { if(comp[idx] != -1) return; comp[idx] = cnt; for(auto &to : rg.g[idx]) rdfs(to, cnt); } }; #line 12 "Contests/yukicoder_/6654/main.cpp" void solve(){ int n, m, l; cin >> n >> m >> l; StronglyConnectedComponents graph(n + m); mf_graph mf(n + m + 2); REP(i, l) { int s, t; cin >> s >> t; s--; t--; graph.add_directed_edge(s, n + t); mf.add_edge(s, n + t, 1); } REP(i, n) mf.add_edge(n + m, i, 1); REP(i, m) mf.add_edge(n + i, n + m + 1, 1); mf.flow(n + m, n + m + 1); REP(i, l) { if(mf.get_edge(i).flow == 1) { graph.add_directed_edge(mf.get_edge(i).to, mf.get_edge(i).from); } } graph.build(); dsu uni(n + m); for(VI &group : graph.group) { REP(i, (int)group.size() - 1) { uni.merge(group[i], group[i + 1]); } } REP(i, l) { int from = mf.get_edge(i).from; int to = mf.get_edge(i).to; if(mf.get_edge(l + from).flow == 0 || mf.get_edge(l + to).flow == 0) { uni.merge(from, to); } } VVI groups = uni.groups(); set single; REP(i, groups.size()) { //assert(groups[i].size() >= 2); if(groups[i].size() == 2) { single.insert(groups[i][0]); single.insert(groups[i][1]); } } REP(i, l) { if(mf.get_edge(i).flow == 0) { print("Yes"); continue; } if(single.count(mf.get_edge(i).from)) print("No"); else print("Yes"); } } // generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) int main() { // Fasterize input/output script ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(100); // scanf/printf user should delete this fasterize input/output script int t = 1; //cin >> t; // comment out if solving multi testcase for(int testCase = 1;testCase <= t;++testCase){ solve(); } return 0; }