//这两题有蛋区别啊，不就差一个要不要把k异或一下么，没看到还害我re了两发
我错了，套路太深……
异或随机化也算是套路了吧……但是还是没想到
瞎jb做一个生成树，给所有非树边随机一个权值，树边的权值等于覆盖他的非树边的权值的异或和
那么如果有一组边的异或和为0的话，基本就可以判断他们是一个树边和覆盖了这个树边的所有非树边
而出现这种情况就说明变得不连通了
也就是说对于输入的每组边判一下是否线性无关即可
707185547最高！
欢迎大家加上面那个QQ，萌汉子哦
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<bitset>
#include<set>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 100010
#define MAXM 500010
#define ull unsigned long long
#define eps 1e-8
#define MOD 1000000007
#define INF 1000000000
struct vec{
int to;
int fro;
int v;
};
vec mp[MAXM*2];
int tai[MAXN],cnt;
int n,m;
int v1[MAXM],v2[MAXM],v[MAXM];
int c[MAXN];
bool te[MAXM];
int fa[MAXN];
bool vis[MAXN];
int pa;
ull b[64];
ull RD(){
return (rand()<<15)+rand();
}
ull rd(){
return (RD()<<30)+RD();
}
inline void be(int x,int y,int z){
mp[++cnt].to=y;
mp[cnt].fro=tai[x];
tai[x]=cnt;
mp[cnt].v=z;
}
inline void bde(int x,int y,int z){
be(x,y,z);
be(y,x,z);
}
void pre(int x){
int i,y;
vis[x]=1;
for(i=tai[x];i;i=mp[i].fro){
y=mp[i].to;
if(!vis[y]){
fa[y]=x;
te[mp[i].v]=1;
pre(y);
}
}
}
void dfs(int x){
int i,y;
for(i=tai[x];i;i=mp[i].fro){
y=mp[i].to;
if(fa[y]==x){
dfs(y);
v[mp[i].v]=c[y];
c[x]^=c[y];
}
}
}
void clr(){
memset(b,0,sizeof(b));
}
bool ins(ull x){
int i;
for(i=63;~i;i--){
if(x&(1ull<<i)){
if(b[i]){
x^=b[i];
}else{
b[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
srand(707185547);
int i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&v1[i],&v2[i]);
bde(v1[i],v2[i],i);
}
pre(1);
for(i=1;i<=m;i++){
if(!te[i]){
v[i]=rd();
c[v1[i]]^=v[i];
c[v2[i]]^=v[i];
}
}
dfs(1);
scanf("%d",&m);
while(m--){
clr();
scanf("%d",&n);
bool flag=1;
for(i=1;i<=n;i++){
scanf("%d",&x);
x^=pa;
flag&=ins(v[x]);
}
pa+=flag;
printf(flag?"Connected\n":"Disconnected\n");
}
return 0;
}
/*
5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13
*/