#include #include using namespace std; using namespace atcoder; // using mint = modint1000000007; // const int mod = 1000000007; // using mint = modint998244353; // const int mod = 998244353; const int INF = 1e9; // const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define P pair template inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; } #ifndef KWM_T_GRAPH_LOWLINK_HPP #define KWM_T_GRAPH_LOWLINK_HPP #include #include #include /** * @brief Lowlink(関節点・橋・2点間の橋必須判定) * * 典型用途: * - 関節点(articulation points)の列挙 * - 橋(bridge)の列挙 * - 辺が s-t パスに必ず含まれるか判定 * * 計算量: * - 構築: O(N + M) * - クエリ: O(1) * * @param グラフは (to, edge_id) を持つ隣接リスト * * 制約 / 注意: * - 無向グラフで使用すること * - edge_id は 0..M-1 の範囲であること * * 使用例: * Lowlink ll(G, M); * ll.build(); * auto aps = ll.articulation_points; * * verified: * - https://yukicoder.me/submissions/1157134 */ namespace kwm_t::graph { class Lowlink { private: using Edge = std::vector>>; public: int sz; int m; Edge G; // 関節点 std::vector articulation_points; // 橋 (edge_id -> 子頂点, -1なら橋でない) std::vector bridge; // DFS木の根 std::vector is_root; private: std::vector in, out, low; std::vector> child; public: Lowlink(const Edge& G, int m) : G(G), m(m) {} void build() { sz = G.size(); in.assign(sz, -1); out.assign(sz, -1); low.assign(sz, -1); child.assign(sz, {}); is_root.assign(sz, false); bridge.assign(m, -1); int k = 0; for (int i = 0; i < sz; ++i) { if (in[i] < 0) { is_root[i] = true; dfs(i, -1, k); } } } /** * @brief 頂点 v を削除したときの連結成分数 */ int remove(int v) const { int c = 0; for (int nv : child[v]) { if (in[v] <= low[nv]) c++; } if (!is_root[v]) c++; return c; } /** * @brief 辺 a が s-t パスに必ず含まれるか */ bool query(int a, int s, int t) const { if (bridge[a] == -1) return false; int l = in[bridge[a]]; int r = out[bridge[a]]; s = in[s]; t = in[t]; return ((l <= s && s < r) ^ (l <= t && t < r)); } private: void dfs(int v, int p_edge, int& k) { in[v] = low[v] = k++; bool is_art = false; for (auto[nv, id] : G[v]) { if (in[nv] < 0) { child[v].push_back(nv); dfs(nv, id, k); low[v] = std::min(low[v], low[nv]); // 関節点判定 if (p_edge != -1 && in[v] <= low[nv]) { is_art = true; } // 橋判定 if (in[v] < low[nv]) { bridge[id] = nv; } } else if (id != p_edge) { low[v] = std::min(low[v], in[nv]); } } // 根の場合 if (p_edge == -1 && child[v].size() >= 2) { is_art = true; } if (is_art) { articulation_points.push_back(v); } out[v] = k++; } }; } // namespace kwm_t::graph #endif // KWM_T_GRAPH_LOWLINK_HPP int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector g(n, vector

()); vector

e(m); rep(i, m) { int u, v; cin >> u >> v; u--, v--; g[u].emplace_back(v, i); g[v].emplace_back(u, i); e[i] = { u,v }; } kwm_t::graph::Lowlink lowlink(g, m); lowlink.build(); auto bridge = lowlink.bridge; dsu uf(n); rep(i, m)if (bridge[i] != -1) { uf.merge(e[i].first, e[i].second); } rep(i, q) { int x, y; cin >> x >> y; x--, y--; if (uf.same(x, y))cout << "Yes" << endl; else cout << "No" << endl; } return 0; }