线段树分治板子题。
根据套路，先将所有操作离线，用线段树分治将删边转化为加边后撤销。
具体而言，记录每个操作有效的时间段，插入到线段树上对应的区间。用可撤销并查集维护连通性，用栈记录已经进行过的操作，以便之后进行撤销。感觉说的了很多没用的，具体还是看代码吧
时间复杂度是 \(\mathcal{O}(q \log q \log n)\)。\(\log q\) 是线段树分治插入的复杂度，\(\log n\) 是可撤销并查集操作一次的复杂度，因为没有路径压缩。
代码：
#include<bits/stdc++.h>
using namespace std;
bool Mbegin;
void File_Work(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
namespace Fast_In_Out{
char buf[1<<21],*P1=buf,*P2=buf;
#define gc (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<21,stdin),P1==P2)?EOF:*P1++)
int read(){
int f=1,x=0;
char c=gc;
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=gc;
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=gc;
}
return f*x;
}
void write(int x){
if(x<0)
x=-x,putchar('-');
if(x>9)
write(x/10);
putchar(x%10+'0');
}
#undef gc
}
using namespace Fast_In_Out;
const int N=1e5+8,M=2e5+8,Q=1e5+8;
int n,m,q;
struct Edge{
int from,to;
}edge[M];
struct Option{
int timl,timr,eid;
}ops[Q*4+M];
int opcnt,lst[M];
bool ans[Q];
struct Disjoint_Set_Union{
int fa[N],siz[N],stc[M],top;
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
}
int find(int x){
return fa[x]==x?x:find(fa[x]);
}
void unite(int x,int y){
stc[++top]=0;
x=find(x),y=find(y);
if(x==y)
return;
if(siz[x]>siz[y])
swap(x,y);
stc[top]=x;
fa[x]=y;
siz[y]+=siz[x];
}
void undo(){
if(stc[top]==0){
top--;
return;
}
siz[fa[stc[top]]]-=siz[stc[top]];
fa[stc[top]]=stc[top];
top--;
}
bool query(){
return siz[find(1)]==n;
}
}dsu;
namespace Segment_Tree_Divide{
vector<int> vec[M<<2];
int ls(int o){
return o<<1;
}
int rs(int o){
return o<<1|1;
}
void insert(int o,int l,int r,int ql,int qr,int eid){
if(ql<=l&&r<=qr){
vec[o].push_back(eid);
return;
}
int mid=(l+r)/2;
if(ql<=mid)
insert(ls(o),l,mid,ql,qr,eid);
if(mid+1<=qr)
insert(rs(o),mid+1,r,ql,qr,eid);
}
void divide(int o,int l,int r){
if(r<l)
return;
for(auto cur:vec[o]){
int u=edge[cur].from,v=edge[cur].to;
dsu.unite(u,v);
}
if(l==r){
ans[l]=dsu.query();
for(int i=0;i<(int)vec[o].size();i++)
dsu.undo();
return;
}
int mid=(l+r)/2;
divide(ls(o),l,mid);
divide(rs(o),mid+1,r);
for(int i=0;i<(int)vec[o].size();i++)
dsu.undo();
}
}
bool Mend;
int main(){
// File_Work();
fprintf(stderr,"%.3lf MB\n\n\n",(&Mbegin-&Mend)/1048576.0);
n=read(),m=read();
dsu.init();
for(int i=1;i<=m;i++){
int u=read(),v=read();
edge[i].from=u;
edge[i].to=v;
lst[i]=1;
}
q=read();
for(int i=1;i<=q;i++){
int c=read();
for(int j=1;j<=c;j++){
int x=read();
opcnt++;
ops[opcnt].timl=lst[x];
ops[opcnt].timr=i-1;
ops[opcnt].eid=x;
lst[x]=i+1;
}
}
for(int i=1;i<=m;i++)
if(lst[i]!=q+1){
opcnt++;
ops[opcnt].timl=lst[i];
ops[opcnt].timr=q;
ops[opcnt].eid=i;
}
for(int i=1;i<=opcnt;i++)
if(ops[i].timl<=ops[i].timr)
Segment_Tree_Divide::insert(1,1,q,ops[i].timl,ops[i].timr,ops[i].eid);
Segment_Tree_Divide::divide(1,1,q);
for(int i=1;i<=q;i++){
if(ans[i]==1)
printf("Connected");
else
printf("Disconnected");
putchar('\n');
}
fprintf(stderr,"\n\n\n%.0lf ms",1e3*clock()/CLOCKS_PER_SEC);
return 0;
}