#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 "<"< struct ListRange { using Iterator= typename std::vector::const_iterator; Iterator bg, ed; Iterator begin() const { return bg; } Iterator end() const { return ed; } size_t size() const { return std::distance(bg, ed); } const T &operator[](int i) const { return bg[i]; } }; template class CsrArray { std::vector csr; std::vector pos; public: CsrArray()= default; CsrArray(const std::vector &c, const std::vector &p): csr(c), pos(p) {} size_t size() const { return pos.size() - 1; } const ListRange operator[](int i) const { return {csr.begin() + pos[i], csr.begin() + pos[i + 1]}; } }; class BipartiteGraph { std::vector> es; std::vector pos, col, ord, pre, mate, blg; CsrArray dag_[2]; int l; public: BipartiteGraph(int n): col(n, -1), pos(n + 1), ord(n), mate(n, -1), blg(n, -3), l(0) {} void add_edge(int u, int v) { es.push_back({u, v}); } void build() { const int n= col.size(); std::vector rt, que(n), g(es.size() * 2); for (auto [u, v]: es) ++pos[u], ++pos[v]; for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i]; for (auto [u, v]: es) g[--pos[u]]= v, g[--pos[v]]= u; for (int s= n, i= 0, t= 0, r= n; s--;) if (col[s] == -1) for (col[s]= 0, ord[l++]= que[t++]= s; i < t; ++i) for (int v= que[i], c= col[v], j= pos[v], u; j < pos[v + 1]; ++j) if (assert(col[u= g[j]] != c); col[u] == -1) col[u]= !c, ord[(c ? l++ : --r)]= que[t++]= u; int t= 0, k= 0; for (bool upd= true; upd; t= 0) { upd= false, rt.assign(n, -1), pre.assign(n, -1); for (int i= l; i--;) if (int v= ord[i]; mate[v] == -1) que[t++]= rt[v]= pre[v]= v; for (int i= 0; i < t; ++i) if (int v= que[i]; mate[rt[v]] == -1) for (int j= pos[v], u, w; j < pos[v + 1]; ++j) { if (w= mate[u= g[j]]; w == -1) { for (upd= true; u != -1; v= pre[v]) mate[u]= v, std::swap(mate[v], u); break; } if (pre[w] == -1) rt[que[t++]= w]= rt[pre[w]= v]; } } for (int i= l; i--;) if (int s= ord[i]; rt[s] != -1) if (blg[s]= -1, s= mate[s]; s != -1) blg[s]= -1; for (int i= l; i < n; ++i) if (int s= ord[i]; mate[s] == -1) blg[que[t++]= s]= 0; for (int i= 0; i < t; ++i) for (int v= que[i], j= pos[v], u, w; j < pos[v + 1]; ++j) if (blg[u= g[j]] == -3) if (w= mate[u], blg[u] == 0; w != -1 && blg[w] == -3) blg[que[t++]= w]= 0; pre.assign(pos.begin(), pos.begin() + n), t= 0; for (int i= l; i--;) if (int v= ord[i]; blg[v] == -3) for (blg[v]= -4; v >= 0;) { if (pre[v] == pos[v + 1]) rt[t++]= v, v= blg[v]; else if (int w= mate[g[pre[v]++]]; blg[w] == -3) blg[w]= v, v= w; } for (int i= 0, e= 0; t--;) if (int s= rt[t], p= mate[s]; blg[p] == -3) for (que[e++]= p, blg[s]= blg[s]= ++k; i < e; ++i) for (int v= que[i], j= pos[v]; j < pos[v + 1]; ++j) if (int u= g[j], w= mate[u]; blg[w] == -3) que[e++]= w, blg[u]= blg[w]= k; pos.assign(++k + 2, 0); for (int v= n; v--; ++pos[blg[v]]) if (blg[v] == -1) blg[v]= k; for (int i= 0; i <= k; ++i) pos[i + 1]+= pos[i]; for (int v= n; v--;) pre[--pos[v]]= v; std::vector> es_; for (auto &[u, v]: es) { if (col[u]) std::swap(u, v); if (int a= blg[u], b= blg[v]; a != b) es_.push_back({a, b}); } std::sort(es_.begin(), es_.end()), es_.erase(std::unique(es_.begin(), es_.end()), es_.end()); std::vector dg0(es_.size()), dg1(es_.size()), sp0(k + 2), sp1(k + 2); for (auto [u, v]: es_) ++sp0[u], ++sp1[v]; std::partial_sum(sp0.begin(), sp0.end(), sp0.begin()), std::partial_sum(sp1.begin(), sp1.end(), sp1.begin()); for (auto [u, v]: es_) dg0[--sp0[u]]= v, dg1[--sp1[v]]= u; dag_[0]= {dg0, sp0}, dag_[1]= {dg1, sp1}; } const std::vector> &edges() const { return es; } bool color(int v) const { return col[v]; } const ListRange left_vertices() const { return {ord.begin(), ord.begin() + l}; } const ListRange right_vertices() const { return {ord.begin() + l, ord.end()}; } int match(int v) const { return mate[v]; } int component_num() const { return pos.size() - 1; } int belong(int v) const { return blg[v]; } const ListRange block(int k) const { return {pre.begin() + pos[k], pre.begin() + pos[k + 1]}; } template const CsrArray &dag() { return dag_[rev]; } std::vector> max_matching() const { std::vector> ret; for (int i= l; i--;) if (int v= ord[i], u= mate[v]; u != -1) ret.push_back({v, u}); return ret; } std::vector min_vertex_cover() const { const int n= col.size(), m= component_num(); std::vector sel(m, -1), ret, que(m); sel[0]= 1, sel.back()= 0; for (int v= 0, k, s, c, i, t; v < n; ++v) { if (c= col[v], s= sel[k= blg[v]]; s == -1) for (sel[k]= s= !c, que[0]= k, i= 0, t= 1; i < t; ++i) for (int u: dag_[c][que[i]]) if (sel[u] == -1) sel[u]= s, que[t++]= u; if (c ^ s) ret.push_back(v); } return ret; } std::vector max_independent_set() const { const int n= col.size(), m= component_num(); std::vector sel(m, -1), ret, que(m); sel[0]= 0, sel.back()= 1; for (int v= 0, k, s, c, i, t; v < n; ++v) { if (c= col[v], s= sel[k= blg[v]]; s == -1) for (sel[k]= s= !c, que[0]= k, i= 0, t= 1; i < t; ++i) for (int u: dag_[s][que[i]]) if (sel[u] == -1) sel[u]= s, que[t++]= u; if (c ^ s) ret.push_back(v); } return ret; } }; using namespace std; namespace yukicoder1745 { // https://yukicoder.me/problems/no/1745 signed main() { cin.tie(0); ios::sync_with_stdio(0); int N, M, L; cin >> N >> M >> L; BipartiteGraph graph(N + M); int S[L], T[L]; for (int i= 0; i < L; ++i) { cin >> S[i] >> T[i]; graph.add_edge(--S[i], T[i]+= N - 1); } graph.build(); for (int i= 0; i < L; ++i) { cout << (graph.belong(S[i]) == graph.belong(T[i]) ? "Yes" : "No") << '\n'; } return 0; } } namespace atcoder_utpc2013_K { // https://atcoder.jp/contests/utpc2013/tasks/utpc2013_11 signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, m; cin >> n >> m; BipartiteGraph graph(n + n); for (int i= 0; i < m; ++i) { int a, b, f; cin >> a >> b >> f; graph.add_edge(--a, --b); } graph.build(); auto ans= graph.min_vertex_cover(); cout << ans.size() << '\n'; for (int x: ans) cout << x + 1 << '\n'; return 0; } } signed main() { cin.tie(0); ios::sync_with_stdio(0); yukicoder1745::main(); // atcoder_utpc2013_K::main(); return 0; }