https://hydro.ac/d/bzoj/p/3569
实际上，考虑类 tarjan 的过程，从这方面入手能更快地有思路。
考虑先找一棵 dfs 树，那么对于未被删去的树边，我们并不需要管。
若对于一条被删去的树边，那么需要底下能返祖！如果底下返不了祖，那么在这里一定就不连通了。换言之，底下的返到这条边以上的边集都被删了。
同时满足两个约束，即该边被删、跨过该边的返祖边被删。直接做应该不太好做，也许是可以做的？
考虑这个约束同时满足，我们能咋做？
我们可以依次考虑每条树边，如果跨过它的边集，我们可以以某种状态表示出来，然后赋给这条树边，那么对于每条被删的树边，我们直接 check 是否存在删的边的子集为该边所记录的状态即可。
那么，考虑随机化权值。发现 xor 以下就好了。
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int M=(int)(5e5+5);
const int N=M;
mt19937 RAND(time(0));
struct edge {
int fr,nex,to,id;
}e[M<<1];
vector<int>vec[M];
ll val[M];
bool is[N],vis[N]; // 1tree 0not tree
int n,m,q,hea[N],cnt,dep[M],tag[M],d[70];
void add_edge(int x,int y,int z) {
e[++cnt].nex=hea[x]; e[cnt].fr=x; e[cnt].to=y; e[cnt].id=z; hea[x]=cnt;
}
void dfs(int x) {
vis[x]=1;
for(int i=hea[x];i;i=e[i].nex) {
int y=e[i].to; if(vis[y]) continue ;
is[e[i].id]=1;
dep[y]=dep[x]+1;
dfs(y);
}
}
void dfs2(int x) {
vis[x]=1;
for(int i=hea[x];i;i=e[i].nex) {
int y=e[i].to; if(vis[y]) continue ;
dfs2(y);
val[e[i].id]^=tag[y]; tag[x]^=tag[y];
}
}
bool ins(int x) {
for(int i=62;i>=0;i--) {
if((x>>i)&1) {
if(!d[i]) {
d[i]=x; return 1;
} else x^=d[i];
}
} return 0;
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++) {
int x,y; cin>>x>>y;
add_edge(x,y,i); add_edge(y,x,i);
}
dfs(1);
for(int i=1;i<=m;i++) if(!is[i]) val[i]=RAND();
for(int i=1;i<=cnt;i+=2) {
if(!is[e[i].id]) {
int x=e[i].fr,y=e[i].to,id=e[i].id;
if(dep[x]<dep[y]) swap(x,y);
tag[x]^=val[id]; tag[y]^=val[id];
// cout<<id<<" "<<x<<" "<<y<<" "<<dep[x]<<" "<<dep[y]<<'\n';
}
}
for(int i=1;i<=n;i++) vis[i]=0;
dfs2(1);
cin>>q; int sum=0;
while(q--) {
int K; cin>>K;
bool ok=1;
for(int i=1;i<=K;i++) {
int x; cin>>x; x^=sum;
if(!ins(val[x])) ok=0;
}
if(ok) ++sum;
if(ok) cout<<"Connected\n";
else cout<<"Disconnected\n";
memset(d,0,sizeof(d));
}
return 0;
}
// n 1e5,m 5e5,q 5e4,k 15