评测结果

#include<bits/stdc++.h>
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define pb push_back
#define mid (l+r>>1)
using namespace std;
const int N=4e5+5;

inline int read() {
    int x=0,w=0; char ch=getchar();
    while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return w?-x:x;
}

struct Edge { int x,y; }e[N];
int n,m,q,k,u,idx,st[N*20];
int fa[N],ch[N][2],cnt,topf,sta[N];
int hd[N<<2],to[N*20],ne[N*20],tc=1;
bool f[N];
vector<int> a[N];

inline void Insert(int,int,int,int,int,int);
inline void Getans(int,int,int);
inline void Rotate(int);
inline void Splay(int);
inline int Getroot(int);
inline void Del(int,int);
inline void Down(int);
inline void Add(int x,int v) { to[++tc]=v; ne[tc]=hd[x]; hd[x]=tc; }
inline void Access(int x) { for(int s=0;x;x=fa[s=x]) Splay(x), rc(x)=s; }
inline void Root(int x) { Access(x); Splay(x); f[x]^=1; swap(lc(x),rc(x)); }
inline void Link(int x,int y) { Root(x); if(Getroot(y)!=x) fa[x]=y; }
inline bool Get(int x) { return rc(fa[x])==x; }
inline bool Isroot(int x) { return lc(fa[x])!=x && rc(fa[x])!=x; }

int main() {
    n=read(); m=read();
    for(int i=1;i<=m;i++) e[i].x=read()+m, e[i].y=read()+m;
    q=read();
    for(int i=1;i<=q;i++) {
        k=read();
        for(int j=1;j<=k;j++) u=read(), a[u].pb(i);
    }
    for(int i=1,las=1,x,y;i<=m;i++,las=1) {
        if(!a[i].size()) {
            x=e[i].x; y=e[i].y;
            if(Getroot(x)!=Getroot(y)) Link(x,i), Link(y,i), cnt++;
            continue;
        }
        a[i].pb(q+1);
        for(int j=0;j<a[i].size();las=a[i][j]+1,j++) 
            if(a[i][j]>1 && las!=n) 
                Insert(1,1,q,las,a[i][j]-1,i);
    }
    Getans(1,1,q);
    return 0;
}

inline void Rotate(int x) {
    int f=fa[x],g=fa[f],o=Get(x),w=ch[x][o^1];
    if(!Isroot(f)) ch[g][Get(f)]=x;
    ch[f][o]=w; ch[x][o^1]=f;
    if(w) fa[w]=f;
    fa[x]=g; fa[f]=x;
}

inline void Splay(int x) {
    int f=0,y=x; sta[topf=1]=x;
    while(!Isroot(y)) sta[++topf]=y=fa[y];
    while(topf) Down(sta[topf--]);
    while(!Isroot(x)) {
        f=fa[x];
        if(!Isroot(f)) Rotate(Get(x)==Get(f)?f:x);
        Rotate(x);
    }
}

inline int Getroot(int x) {
    Access(x); Splay(x);
    while(lc(x)) Down(x), x=lc(x);
    return Splay(x), x;
}

inline void Del(int x,int y) {
    Root(x);
    if(Getroot(y)!=x || fa[y]!=x || lc(y)) return ;
    fa[y]=rc(x)=0; 
}

inline void Down(int k) {
    if(!f[k]) return ;
    if(lc(k)) f[lc(k)]^=1, swap(lc(lc(k)),rc(lc(k)));
    if(rc(k)) f[rc(k)]^=1, swap(lc(rc(k)),rc(rc(k)));
    f[k]=0;
}

inline void Insert(int k,int l,int r,int L,int R,int p) {
    if(L>R) return ;
    if(L<=l && R>=r) return Add(k,p);
    if(L<=mid) Insert(k<<1,l,mid,L,R,p);
    if(R>mid) Insert(k<<1|1,mid+1,r,L,R,p);
}

inline void Getans(int k,int l,int r) {
    int it=idx;
    for(int i=hd[k],p,x,y;i;i=ne[i]) {
        p=to[i]; x=e[p].x; y=e[p].y;
        if(Getroot(x)!=Getroot(y)) {
            lc(p)=rc(p)=fa[p]=0;
            Link(x,p), Link(y,p), cnt++, st[++idx]=p;
        }
    }
    if(l==r) {
        if(cnt==n-1) puts("Connected");
        else puts("Disconnected");
    }
    else Getans(k<<1,l,mid), Getans(k<<1|1,mid+1,r);
    int p;
    while(idx>it) 
        p=st[idx--], 
        Del(p,e[p].x), Del(p,e[p].y), cnt--; 
}