#include #include #define rep(i,b) for(int i=0;i=0;i--) #define rep1(i,b) for(int i=1;i using mpq = priority_queue, greater>; template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (b ll sumv(const vector&a){ll res(0);for(auto&&x:a)res+=x;return res;} bool yn(bool a) { if(a) {cout << "Yes" << endl; return 1;} else {cout << "No" << endl; return 0;}} #define dame { cout << "No" << endl; return 0;} #define dame1 { cout << -1 << endl; return 0;} #define test(x) cout << "test" << x << endl; #define deb(x,y) cout << x << " " << y << endl; #define deb3(x,y,z) cout << x << " " << y << " " << z << endl; #define deb4(x,y,z,x2) cout << x << " " << y << " " << z << " " << x2 << endl; #define out cout << ans << endl; #define outv fore(yans , ans) cout << yans << "\n"; #define show(x) cerr<<#x<<" = "<; using pil = pair; using pli = pair; using pii = pair; using tp = tuple; using vi = vector; using vl = vector; using vs = vector; using vb = vector; using vpii = vector; using vpli = vector; using vpll = vector; using vpil = vector; using vvi = vector>; using vvl = vector>; using vvs = vector>; using vvb = vector>; using vvpii = vector>; using vvpli = vector>; using vvpll = vector; using vvpil = vector; using mint = modint998244353; using vm = vector; using vvm = vector>; vector dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1}; ll gcd(ll a, ll b) { return a?gcd(b%a,a):b;} ll lcm(ll a, ll b) { return a/gcd(a,b)*b;} const double eps = 1e-10; const ll LINF = 1001002003004005006ll; const int INF = 1001001001; template struct lca { int n, root, l; vector> to; vector> co; vector dep; vector costs; vector> par; lca(int n):n(n),to(n),co(n),dep(n),costs(n) { l = 0; while ((1<>(n+1,vector(l,n)); } void add_edge(int a, int b, T c=0) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void dfs(int v, int d=0, T c=0, int p=-1) { if (p != -1) par[v][0] = p; dep[v] = d; costs[v] = c; for (int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if (u == p) continue; dfs(u, d+1, c+co[v][i], v); } } void init(int _root=0) { root = _root; dfs(root); for (int i = 0; i < l-1; ++i) { for (int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } // LCA int operator()(int a, int b) { if (dep[a] > dep[b]) swap(a,b); int gap = dep[b]-dep[a]; for (int i = l-1; i >= 0; --i) { int len = 1<= len) { gap -= len; b = par[b][i]; } } if (a == b) return a; for (int i = l-1; i >= 0; --i) { int na = par[a][i]; int nb = par[b][i]; if (na != nb) a = na, b = nb; } return par[a][0]; } int length(int a, int b) { int c = lca(a,b); return dep[a]+dep[b]-dep[c]*2; } T dist(int a, int b) { int c = lca(a,b); return costs[a]+costs[b]-costs[c]*2; } }; // 初期化方法 lca g(n) :: nは頂点数、T1はコストのタイプ // g.add_edge(a,b,c) :: a,b間にコストcの辺をはる。cは省略可(0となる)。 // g.dfs(v) :: vからdfs。各頂点の深さと根からの到達コストを計算。 // g.init() :: ダブリングにより各頂点の2^i個上の親を計算。結果はpar[v][i]に入る。 // g(a,b) :: 頂点a,bのlcaを出力。 // g.length(a,b) :: 頂点a,b間の辺の数を出力。 // g.dist(a,b) :: 頂点a,b間のコストを出力。 vvi e; int n; vl va; map mp; unordered_map mpnr; unordered_map mpn; vb flg; int dfs(int x,int pre){ int ret = va[x]; fore(ytmp , e[mpnr[x]]){ int y = mpn[ytmp]; if(y == pre) continue; ret += dfs(y ,x); } if (ret != 0 && pre != -1) flg[mp[{mpnr[x] , mpnr[pre]}]] = true; return ret; } int main(){ int m,q; cin>>n>>m>>q; vvi res(n); vvi to(n); dsu d(n); e.resize(n); va.resize(n); flg.resize(m); rep(i,m){ int a,b; cin>>a>>b; a--; b--; mp[{a,b}] = i; mp[{b,a}] = i; if (d.same(a,b)) res[a].pb(b); else{ d.merge(a,b); to[a].pb(b); e[a].pb(b); e[b].pb(a); } } vvi v = d.groups(); fore(y , v){ if (sz(mpnr)) assert(0); int ts = sz(y); lca tr(ts); int k = 0; fore(yy , y){ mpn[yy] = k; mpnr[k++] = yy; } fore(yy , y){ fore(ey , to[yy]) tr.add_edge(mpn[ey] , mpn[yy]); } tr.init(); fore(yy , y){ fore(ey , res[yy]){ int a = mpn[yy]; int b = mpn[ey]; int c = tr(a , b); va[a] += 1; va[b] += 1; va[c] -= 2; flg[mp[{yy , ey}]] = true; } } dfs(y[0] , -1); mpnr.clear(); mpn.clear(); rep(i,k) va[i] = 0; } dsu d2(n); rep(i,n){ fore(y , to[i]){ int j = mp[{y , i}]; if (!flg[j]) d2.merge(y , i); } } vb ans(q); rep(i,q){ int a,b; cin>>a>>b; a--; b--; ans[i] = d2.same(a,b); } fore(y , ans) yn(y); return 0; }