$n leq 1e5,m leq 2e5$的无向图，每次问：删若干$(leq 15)$条边图是否连通。
3563和3569就不写了。。三倍
建个图的dfs树，非树边带随机权，点权为从其出发的所有非树边权异或和，树边的权值为其子树内点权异或和。如此当一棵子树被完全切下来时，会有一些选中的边权异或和为0.
异或和为0时，一定会选中树边，选中的树边的子树会与外层点脱离。
因此线性基判断即可。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 //#include<time.h> 5 //#include<complex> 6 //#include<set> 7 //#include<queue> 8 #include<algorithm> 9 #include<stdlib.h> 10 using namespace std; 11 12 #define LL long long 13 int qread() 14 { 15 char c; int s=0; while ((c=getchar())<'0' || c>'9'); 16 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s; 17 } 18 19 //Pay attention to '-' , LL and double of qread!!!! 20 21 int n,m,lq; 22 #define maxn 100011 23 #define maxm 400011 24 struct Edge{int to,next;}edge[maxm]; int first[maxn],ve[maxm],le=2; 25 void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;} 26 void insert(int x,int y) {in(x,y); in(y,x);} 27 28 int Rand() {return (rand()<<15)+rand()+1;} 29 30 struct JI 31 { 32 int a[33]; 33 void clear() {memset(a,0,sizeof(a));} 34 bool insert(int v) 35 { 36 for (int i=30;~i && v;i--) if ((v>>i)&1) 37 { 38 if (!a[i]) {a[i]=v; return 1;} 39 v^=a[i]; 40 } 41 return 0; 42 } 43 }ji; 44 45 int val[maxn],dep[maxn]; bool vis[maxn]; 46 void dfs(int x,int fa) 47 { 48 vis[x]=1; 49 for (int i=first[x];i;i=edge[i].next) 50 { 51 Edge &e=edge[i]; if (e.to==fa) continue; 52 if (vis[e.to]) 53 { 54 if (!ve[i]) ve[i]=ve[i^1]=Rand(),val[e.to]^=ve[i],val[x]^=ve[i]; 55 } 56 else dep[e.to]=dep[x]+1,dfs(e.to,x),val[x]^=val[e.to]; 57 } 58 // cout<<x<<' '<<val[x]<<' '<<dep[x]<<endl; 59 } 60 61 int main() 62 { 63 srand(19260817); 64 n=qread(); m=qread(); 65 for (int i=1;i<=m;i++) insert(qread(),qread()); 66 dfs(1,0); 67 // for (int i=2;i<le;i+=2) cout<<ve[i]<<' ';cout<<endl; 68 lq=qread(); 69 for (int i=1,x,y;i<=lq;i++) 70 { 71 ji.clear(); 72 x=qread(); 73 bool flag=1; 74 for (int j=1;j<=x;j++) 75 { 76 y=qread(); 77 if (flag) 78 { 79 if (ve[y<<1]) flag=ji.insert(ve[y<<1]); 80 else flag=ji.insert(val[dep[edge[y<<1].to]>dep[edge[(y<<1)|1].to]? 81 edge[y<<1].to:edge[(y<<1)|1].to]); 82 } 83 } 84 puts(flag?"Connected":"Disconnected"); 85 } 86 return 0; 87 }