#ifdef t9unkubj #include"template.h" //#include"template_no_debug.h" #else #undef _GLIBCXX_DEBUG #pragma GCC optimize("O3") #define dbg(...) 199958 using namespace std; #include using uint=unsigned; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; templateusing vc=vector; templateusing vvc=vc>; templateusing vvvc=vvc>; using vi=vc; using vvi=vc; using vvvi=vc; using vl=vc; using vvl=vc; using vvvl=vc; templateusing smpq=priority_queue,greater>; templateusing bipq=priority_queue; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define mp make_pair #define pb push_back #define eb emplace_back #define fi first #define se second #define is insert #define bg begin() #define ed end() void scan(int&a) { cin >> a; } void scan(ll&a) { cin >> a; } void scan(string&a) { cin >> a; } void scan(char&a) { cin >> a; } void scan(uint&a) { cin >> a; } void scan(ull&a) { cin >> a; } void scan(bool&a) { cin >> a; } void scan(ld&a){ cin>> a;} template void scan(vector&a) { for(auto&x:a) scan(x); } void read() {} template void read(Head&head, Tail&... tail) { scan(head); read(tail...); } #define INT(...) int __VA_ARGS__; read(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__); #define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__); #define STR(...) string __VA_ARGS__; read(__VA_ARGS__); #define CHR(...) char __VA_ARGS__; read(__VA_ARGS__); #define DBL(...) double __VA_ARGS__; read(__VA_ARGS__); #define LD(...) ld __VA_ARGS__; read(__VA_ARGS__); #define VC(type, name, ...) vector name(__VA_ARGS__); read(name); #define VVC(type, name, size, ...) vector> name(size, vector(__VA_ARGS__)); read(name); void print(int a) { cout << a; } void print(ll a) { cout << a; } void print(string a) { cout << a; } void print(char a) { cout << a; } void print(uint a) { cout << a; } void print(bool a) { cout << a; } void print(ull a) { cout << a; } void print(double a) { cout << a; } void print(ld a){ cout<< a; } template void print(vectora) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout< void PRT(T a) { print(a); cout < void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; } template bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template bool chmax(T &x, F y){ if(x int popcount(T n){ return __builtin_popcountll(n); } template T sum(vc&a){ return accumulate(all(a),T(0)); } template T max(vc&a){ return *max_element(all(a)); } template T min(vc&a){ return *min_element(all(a)); } template void unique(vc&a){ a.erase(unique(all(a)),a.end()); } vvi readgraph(int n,int m,int off = -1){ vvi g(n); rep(i, m){ int u,v; cin>>u>>v; u+=off,v+=off; g[u].push_back(v); g[v].push_back(u); } return g; } vvi readtree(int n,int off=-1){ return readgraph(n,n-1,off); } template vc presum(vc &a){ vc ret(a.size()+1); rep(i,a.size())ret[i+1]=ret[i]+a[i]; return ret; } template vc &operator+=(vc &a,F b){ for (auto&v:a)v += b; return a; } template vc &operator-=(vc&a,F b){ for (auto&v:a)v-=b; return a; } template vc &operator*=(vc&a,F b){ for (auto&v:a)v*=b; return a; } #endif /* https://atcoder.jp/contests/arc039/tasks/arc039_d https://kntychance.hatenablog.jp/entry/2022/09/16/161858 */ struct Edge{ int from; int to; int id; }; struct graph{ vector>g; vectorlow,ord; vectorea,eb; vectorused; int n; graph(int n):n(n),g(n),low(n),ord(n){} int edge_num=0; void add_edge(int a,int b,int is_both=1){ g[a].push_back({a,b,edge_num}); if(is_both)g[b].push_back({b,a,edge_num}); ea.push_back(a); eb.push_back(b); used.push_back(0); edge_num++; } struct cycle_scanner{ vectorseen,finish; vectorhist; int n; vector>g; cycle_scanner(vector>g):g(g),n(g.size()){ } int dfs(int now,const Edge&pre,int can_rev){ seen[now]=1; hist.push_back(pre); for(auto&e:g[now]){ if(can_rev==0&&pre.id==e.id)continue; if(finish[e.to]){ continue; } if(seen[e.to]&&!finish[e.to]){ hist.push_back(e); return e.to; } int res=dfs(e.to,e,can_rev); if(res!=-1)return res; } finish[now]=1; hist.pop_back(); return -1; } vectorconstructer(int pos){ vectorres; while(hist.size()){ auto p=hist.back();hist.pop_back(); res.push_back(p); if(p.from==pos)break; } reverse(res.begin(), res.end()); return res; } //有向グラフなら1,そうでないなら0を与える vectorfind_v(int can_rev){ seen.resize(n),finish.resize(n); int pos=-1; for(int i=0;i cycle_scan(int can_rev){ cycle_scanner cyc(g); return cyc.find_v(can_rev); } int lowlinked=0; void lowlink(){ if(lowlinked)return; lowlinked=1; vectorseen(n); auto dfs=[&](auto&dfs,int u,int v,int&now)->int{ seen[u]=1; ord[u]=now++; low[u]=ord[u]; for(auto [from,x,i]:g[u]){ if(i==v)continue; if(seen[x]){ low[u]=min(low[u],ord[x]); }else{ used[i]=1; low[u]=min(low[u],dfs(dfs,x,i,now)); } } return low[u]; }; int now=0; for(int i=0;itwo_comp_num; vector>two_comp; void make_two_comp(){ if(two_comp.size())return; lowlink(); two_comp_num=vector(n); vector>res; dfs1(0,-1,res); for(int i=0;i&vs); int is_bridge(int i){ if(!used[i])return 0; int a1=ea[i],a2=eb[i]; if(ord[a1]>ord[a2])swap(a1,a2); if(ord[a1]>=low[a2])return 0; return 1; } void dfs1(int u,int v,vector>&res){ vectorvs{u}; for(auto [_,x,i]:g[u]){ if(x==v)continue; if(!used[i])continue; if(!is_bridge(i)){ dfs2(x,u,res,vs); }else{ dfs1(x,u,res); } } res.push_back(vs); } void dfs2(int u,int v,vector>&res,vector&vs){ vs.push_back(u); for(auto [_,x,i]:g[u]){ if(x==v)continue; if(!used[i])continue; if(!is_bridge(i)){ dfs2(x,u,res,vs); }else{ dfs1(x,u,res); } } } vector>two_g;//二重辺連結成分分解して成分ごとに縮約した気 void make_two_g(){ make_two_comp(); auto res=two_comp; two_g.resize(res.size()); for(int i=0;i<(int)ea.size();i++){ if(two_comp_num[ea[i]]!=two_comp_num[eb[i]]){ two_g[two_comp_num[ea[i]]].push_back(two_comp_num[eb[i]]); two_g[two_comp_num[eb[i]]].push_back(two_comp_num[ea[i]]); } } } //https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_A vectoris_art; void make_art(){ lowlink(); is_art.resize(n); int res=0; for(auto [_,x,i]:g[0]){ if(used[i])res++; } is_art[0]=res>=2; for(int i=1;i>> bc;//おなじ連結成分に属している辺 vector>bcs;//頂点 void bic(){ lowlink(); vectorused(n); vector>tmp; auto dfs=[&](auto&dfs,int u,int v)->void{ used[u]=1; for(auto [_,x,idx]:g[u]){ if(x==v)continue; if(!used[x]||ord[x]=ord[u]){ bc.push_back(vector>()); while(1){ auto p=tmp.back();tmp.pop_back(); bc.back().push_back(p); if(p.first==min(x,u)&&p.second==max(x,u)){ break; } } } } } if(g[u].size()==0){//孤立点 bcs.push_back(vector{u}); } }; for(int i=0;iadded(n); for(auto x:bc){ bcs.push_back(vector()); for(auto [a,b]:x){ auto add=[&](int x){ if(added[x])return; bcs.back().push_back(x); added[x]=1; }; add(a),add(b); } for(auto x:bcs.back())added[x]=0; } } }; double pass_time=0; template struct base_dsu{ vectorpar; vectordata; base_dsu(int n):par(n,-1){ static_assert(!extra,"e is needed"); } base_dsu(int n,T e):par(n,-1),data(n,e){} T& operator[](int i){ static_assert(extra,"No data"); return data[leader(i)]; } int root(int x){ if(par[x]<0)return x; else return par[x]=root(par[x]); } bool same(int x,int y){ return root(x)==root(y); } bool merge(int x,int y){ x=root(x); y=root(y); if(x==y)return false; if(par[x]>par[y])swap(x,y); par[x]+=par[y]; par[y]=x; if(extra){ data[x]=op(data[y],data[x]); } return true; } int size(int x){ return -par[root(x)]; } int leader(int x){ return root(x); } }; int tf323(int a,int b){return a;} using dsu=base_dsu; template using extra_dsu=base_dsu; void solve(){ INT(n,m,q); graph g(n); vi a(m),b(m); rep(i,m){ cin>>a[i]>>b[i]; --a[i],--b[i]; g.add_edge(a[i],b[i],1); } g.lowlink(); dsu dsu(n); rep(i,m)if(g.is_bridge(i))dsu.merge(a[i],b[i]); while(q--){ INT(x,y); --x,--y; YesNo(dsu.same(x,y)); } } signed main(){ cin.tie(0)->sync_with_stdio(0); pass_time=clock(); int t=1; //cin>>t; while(t--)solve(); pass_time=clock()-pass_time; dbg(pass_time/CLOCKS_PER_SEC); }