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\)也异或了答案，我们只要看读了几条边就可知道答案了。 呵呵，我还写的正解(见BZOJ 3569 DZY Loves Chinese II)。。。

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

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 <int> 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<<i))

			{

				swap(bit[now],bit[j]);

				break;

			}

		if (bit[now]&(1<<i))

		{

			for (int j = 1;j <= K;++j)

				if (j != now&&(bit[j]&(1<<i))) bit[j] ^= bit[now];

			++now;

		}

	}

	for (int i = 1;i <= 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;

}