本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ3237
正解：$CDQ$分治
解题报告：
考虑直接做的话很难维护图的连通性，$yy$了一下$LCT$似乎可做？
不过既然是学图分治的就写一发$CDQ$分治吧…
考虑我把没有被删除过的所有边所连接的点，看做一个点，用并查集合并起来，这样能降低图的规模。
我每次处理区间为$[l,r]$的询问，当我做$[l,mid]$即左边时，我可以把右边需要删除的边全部加入图中，这样就不会对左边造成影响，然后递归左边，反过来再做一次右边。
并查集每次需要恢复到历史状态，这只需要用一个栈把修改的地方存下来就可以了。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 400011;
const int MAXM = 200011;
int n,m,Q,ans[MAXN],top,stack[MAXN];
int size[MAXN],cnt[MAXN],father[MAXN];
struct edge{ int x,y; }e[MAXM];
struct ask{ int num,a[5]; }q[MAXN];
inline int find(int x){ if(father[x]!=x) return find(father[x]);/*!!!*/ return father[x]; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void Union(int x,int y){
if(size[x]>size[y]) swap(x,y);
father[x]=y; size[y]+=size[x]; stack[++top]=x;
}
inline void recover_stack(int di){
int x;
while(top>di) {
x=stack[top];
size[father[x]]-=size[x];
father[x]=x;
top--;
}
}
inline void CDQ(int l,int r){
if(l==r) {
if(size[find(1)]==n) ans[l]=1;
else ans[l]=0;
return ;
}
int mid=(l+r)>>1,tt=top,x,y;
for(int i=mid+1;i<=r;i++) {
for(int j=0;j<q[i].num;j++) {
cnt[ q[i].a[j] ]--;
if(cnt[ q[i].a[j] ]!=0) continue;
x=e[ q[i].a[j] ].x; y=e[ q[i].a[j] ].y;
x=find(x); y=find(y);
if(x!=y) Union(x,y);
}
}
CDQ(l,mid);
for(int i=mid+1;i<=r;i++)
for(int j=0;j<q[i].num;j++)
cnt[ q[i].a[j] ]++;
recover_stack(tt);
for(int i=l;i<=mid;i++) {
for(int j=0;j<q[i].num;j++) {
cnt[ q[i].a[j] ]--;
if(cnt[ q[i].a[j] ]!=0) continue;
x=e[ q[i].a[j] ].x; y=e[ q[i].a[j] ].y;
x=find(x); y=find(y);
if(x!=y) Union(x,y);
}
}
CDQ(mid+1,r);
for(int i=l;i<=mid;i++)
for(int j=0;j<q[i].num;j++)
cnt[ q[i].a[j] ]++;
recover_stack(tt);
}
inline void work(){
n=getint(); m=getint(); for(int i=1;i<=m;i++) e[i].x=getint(),e[i].y=getint();
Q=getint(); int x,y;
for(int i=1;i<=Q;i++) {
q[i].num=getint();
for(int j=0;j<q[i].num;j++)
q[i].a[j]=getint(),cnt[q[i].a[j]]++;
}
for(int i=1;i<=n;i++) father[i]=i,size[i]=1;
for(int i=1;i<=m;i++) {
if(cnt[i]==0) {
x=e[i].x; y=e[i].y;
x=find(x); y=find(y);
if(x!=y) {
if(size[x]>size[y]) swap(x,y);
father[x]=y; size[y]+=size[x];
}
}
}
CDQ(1,Q);
for(int i=1;i<=Q;i++)
if(ans[i]) puts("Connected");
else puts("Disconnected");
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。