1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
int n, m, uu[500005], vv[500005], cc[500005], cnt, val[500005], k;
int ji[33], hea[100005];
bool vis[100005], iss[500005];
struct Edge{
int too, nxt, idx;
}edge[1000005];
void add_edge(int fro, int too, int idx){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
edge[cnt].idx = idx;
hea[fro] = cnt;
}
void rn(int &x){
x = 0;
char ch=getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
}
int rnd(){
return (long long)rand()*rand()%1000000000+1;
}
void dfs1(int x, int f){
vis[x] = true;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f && !vis[t]){
dfs1(t, x);
iss[edge[i].idx] = true;
}
}
}
void dfs2(int x, int f){
vis[x] = true;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f && iss[edge[i].idx]){
dfs2(t, x);
val[x] ^= val[t];
cc[edge[i].idx] = val[t];
}
}
}
int main(){
srand(time(NULL));
cin>>n>>m;
for(int i=1; i<=m; i++){
rn(uu[i]); rn(vv[i]);
add_edge(uu[i], vv[i], i);
add_edge(vv[i], uu[i], i);
}
dfs1(1, 0);
for(int i=1; i<=m; i++)
if(!iss[i]){
cc[i] = rnd();
val[uu[i]] ^= cc[i];
val[vv[i]] ^= cc[i];
}
memset(vis, 0, sizeof(vis));
dfs2(1, 0);
int ans=0, q, uu;
cin>>q;
while(q--){
rn(k);
bool flag=true;
memset(ji, 0, sizeof(ji));
while(k--){
rn(uu); uu ^= ans;
uu = cc[uu];
for(int i=31; i>=0; i--)
if(uu&(1<<i)){
if(!ji[i]){
ji[i] = uu;
break;
}
else uu ^= ji[i];
}
if(!uu) flag = false;
}
if(!flag) printf("Disconnected\n");
else{
printf("Connected\n");
ans++;
}
}
return 0;
}
|