#include #include namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyList(int n, std::vector> edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = v; if(rev) E[--buf[v]] = u; } I = std::move(buf); } AdjacencyList(const std::vector>& edges = {}){ int n = mn = edges.size(); std::vector buf(n+1, 0); for(int i=0; i targets, std::vector bounds){ AdjacencyList res; res.mn = bounds.size() - 1; res.E = std::move(targets); res.I = std::move(bounds); return res; } AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyList reversed_edges() const { AdjacencyList res; int n = res.mn = mn; std::vector buf(n+1, 0); for(int v : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Edge& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyListEdgeIndexed(int n, const std::vector>& edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = { v, i }; if(rev) E[--buf[v]] = { u, i }; } I = std::move(buf); } AdjacencyListEdgeIndexed() : AdjacencyListEdgeIndexed(0, {}, false) {} AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyListEdgeIndexed reversed_edges() const { AdjacencyListEdgeIndexed res; int n = res.mn = mn; std::vector buf(n+1, 0); for(auto [v,i] : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u> medges; ::std::vector edgeidx_to_bcidx; public: BiconnectedComponents(int n, ::std::vector<::std::pair> edges){ // after dfs1 ... inverse of dfsi_to_vtx ::std::vector vtx_to_dfsi; // not visited by dfs1 ... -1 // visited by dfs1 ... (the parent of parent of v and v would be cut when we delete the parent of v) ? 1 : 0 ::std::vector linked_over; // not visited by dfs1 ... -1 // visited by dfs1 and no parent in the dfs tree ... -2 // otherwise ... the parent edge ::std::vector dfs_parent; // parent vtx ::std::vector dfs_parentp; ::std::vector dfs_backedge; mn = n; int m = edges.size(); medges = std::move(edges); AdjacencyListEdgeIndexed adj(n, medges, true); vtx_to_dfsi.resize(n); dfs_parent.assign(n, -1); dfs_parentp.assign(n, -1); dfs_backedge.assign(n, -1); int dfsi = 0; int num_bcs = 0; ::std::vector res(m); ::std::vector mem(n*2); int memi = 0; for(int i=0; i cut } } } } edgeidx_to_bcidx = ::std::move(res); mm = m; mnum_bcs = num_bcs; } int get_num_bcts() const { return mnum_bcs; } ::std::vector<::std::vector> get_bcs() const { ::std::vector<::std::vector> res(mnum_bcs); for(int i=0; i buf(mnum_bcs+1); for(int bci : edgeidx_to_bcidx) ++buf[bci]; for(int i=1; i<=mnum_bcs; i++) buf[i] += buf[i-1]; ::std::vector E(buf.back()); for(int i=0; i> res(bct_n - 1); int resi = 0; ::std::vector visited(mn); for(int bci=0; bci namespace nachia { struct Dsu{ private: std::vector w; public: Dsu(int n) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int merge(int u, int v){ u = leader(u); v = leader(v); if(-w[u] < -w[v]) std::swap(u, v); else if(w[u] == w[v]) w[u]--; w[v] = u; return u; } bool same(int u, int v){ return leader(u) == leader(v); } }; } // namespace nachia #include #include #include using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using modint = atcoder::static_modint<1000000007>; int main(){ int N; cin >> N; int M; cin >> M; int Q; cin >> Q; vector> edges(M); rep(i,M){ int u; cin >> u; u--; int v; cin >> v; v--; edges[i] = make_pair(u,v); } auto bcs = nachia::BiconnectedComponents(N, edges); vector> new_edges; for(auto& bc : bcs.get_bcs()) if(bc.size() == 1) new_edges.push_back(edges[bc[0]]); nachia::Dsu dsu(N); for(auto [u,v] : new_edges) dsu.merge(u,v); rep(i,Q){ int u; cin >> u; u--; int v; cin >> v; v--; bool ans = dsu.same(u,v); cout << (ans ? "Yes\n" : "No\n"); } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;