Description

神校XJ之学霸兮，Dzy皇考曰JC。
摄提贞于孟陬兮，惟庚寅Dzy以降。
纷Dzy既有此内美兮，又重之以修能。
遂降临于OI界，欲以神力而凌♂辱众生。
今Dzy有一魞歄图，其上有\(N\)座祭坛，又有\(M\)条膴蠁边。
时而Dzy狂WA而怒发冲冠，神力外溢，遂有\(K\)条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。（可视为立即复原）
然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。

Input

第一行\(N,M\)。
接下来\(M\)行\(x,y\)：表示\(M\)条膴蠁边，依次编号。
接下来一行\(Q\)。
接下来\(Q\)行：
每行第一个数\(K\)而后\(K\)个编号\(c_{1} \sim c_{K}\)：表示\(K\)条边，编号为\(c_{1} \sim c_{K}\)。
为了体现在线，K以及\(c_{1} \sim c_{K}\)均需异或之前回答为连通的个数。

Output

对于每个询问输出：连通则为‘Connected’，不连通则为‘Disconnected’（不加引号）

Sample Input

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
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13

Sample Output

Connected
Connected
Connected
Connected
Disconnected

HINT

\(N \le 100000,M \le 500000,Q \le 50000,1 \le K \le 15\)
数据保证没有重边与自环

逗比题，考验语文能力。由于\(K\)也异或了答案，我们只要看读了几条边就可知道答案了。呵呵，我还写的正解(见)。。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn (100010)#define maxm (1000010)int K,n,m,father[maxn],bit[maxn],dep[maxn],ans;int side[maxn],next[maxm*2],toit[maxm*2],num = 1,up[maxn];bool exist[maxm],sign; vector 
         
           ch[maxn];inline int getint(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void add(int a,int b) { next[++num] = side[a]; side[a] = num; toit[num] = b; } inline void ins(int a,int b) { add(a,b); add(b,a); }struct node{ int u,v,w; inline void read() { u = getint(),v = getint(); ins(u,v); } }edge[maxm];inline int find(int a) { if (father[a] != a) father[a] = find(father[a]); return father[a]; }inline void dfs(int now,int fa){ for (int i = side[now];i;i = next[i]) { if (toit[i] == fa||!exist[i>>1]) continue; up[toit[i]] = i,ch[now].push_back(toit[i]),dep[toit[i]] = dep[now]+1,dfs(toit[i],now); }}inline void deal(int a,int b,int w){ if (dep[a] < dep[b]) swap(a,b); while (dep[a] != dep[b]) { edge[up[a]>>1].w ^= w; a = toit[up[a]^1]; } if (a == b) return; while (a != b) { edge[up[a]>>1].w ^= w; a = toit[up[a]^1]; edge[up[b]>>1].w ^= w; b = toit[up[b]^1]; }}inline void ready(){ for (int i = 1;i <= n;++i) father[i] = i; int cnt = 0; for (int i = 1;i <= m;++i) { int r1 = find(edge[i].u),r2 = find(edge[i].v); if (r1 != r2) ++cnt,father[r1] = r2,exist[i] = true; if (cnt == n-1) break; } dfs(1,0); for (int i = 1;i <= m;++i) if (!exist[i]) edge[i].w = rand()%(1<<30),deal(edge[i].u,edge[i].v,edge[i].w);}inline bool connect(){ int now = 1; for (int i = 29;i >= 0&&now <= K;--i) { for (int j = now;j <= K;++j) if (bit[j] & (1<
          
           <= K;++j) if (j != now&&(bit[j]&(1<
           
            <= K;++i) if (!bit[i]) return false; return true;}int main(){ freopen("3563.in","r",stdin); freopen("3563.out","w",stdout); srand(19980402); n = getint(),m = getint(); for (int i = 1;i <= m;++i) edge[i].read(); ready(); int Q = getint(); while (Q--) { K = getint(); K ^= ans; for (int i = 1;i <= K;++i) { int a = getint(); a ^= ans; bit[i] = edge[a].w; } sign = connect(); if (sign) puts("Connected"); else puts("Disconnected"); ans += sign; } return 0;}