Exclusive-OR

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2311    Accepted Submission(s): 645

You are not given n non-negative integers
X₀, X₁, ..., X_n-1 less than 2²⁰ , but they do exist, and their values never change.
I'll gradually provide you some facts about them, and ask you some questions.
There are two kinds of facts, plus one kind of question:

2 6
I 0 1 3
Q 1 0
Q 2 1 0
I 0 2
Q 1 1
Q 1 0
3 3
I 0 1 6
I 0 2 2
Q 2 1 2
2 4
I 0 1 7
Q 2 0 1
I 0 1 8
Q 2 0 1
0 0

Case 1:
I don't know.
3
1
2
Case 2:
4
Case 3:
7
The first 2 facts are conflicting.

/*
HDU 3234 并查集扩展 
有n(n<=20000)个未知的整数X0,X1,X2Xn-1，有以下Q个(Q<=40000)操作： 
I p v :告诉你Xp=v 
I p q v :告诉你Xp Xor Xq=v 
Q k p1 p2 … pk : 询问 Xp1 Xor Xp2 .. Xor Xpk， k不大于15。 
如果当前的I跟之前的有冲突的话，跳出    

并查集扩展！
于I p v ，如果虚设一个点Xn=0,则可以看成 I p n v（与0异或）
所以对于所有那些I，都是a^b=v，两个两个的，连带的效果
所以设val[i]=Xi^Xfa[i] 跟上面一样有连带效果 fa[i]为i的父亲
这样：
1) I p q v
先find
如果p q在同一集合，判断是否有Xp^Xq=v 不是的话矛盾
否则，合并  注意虚设的点n要始终保持为根

如果pre[a]=ra,pre[b]=rb;那么合并之后是什么情况呢，
即r[a]=num[a]^num[ra];r[b]=num[b]^num[rb];以因为r[a]^r[b]=c
现在要求的是num[ra]=num[ra]^num[rb]=r[a]^r[b]^c;

给出的条件有两个，如果只是单个结点的该怎么办呢，加入一个冗余结点就行了，
标号为n,值为0，任何数和0异或还为本身。

剩下的是查询，如果查询的某个数存在于某个集合中。
如果根为我们加入的冗余结点，那么显然r[x]=num[x]，
直接异或起来就行了。
如果不是冗余结点，r[x]=r[x]^r[pre[x]]，则多异或了一次根结点，
如果某个集合中的个数为偶数，那么偶数次异或，刚好把根消掉，
如果为奇数则说明不可判断。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 20005
int pre[N],r[N];
int n,q;
int k,num[N];
char ope[1000];
vector<int>que;
void init()
{
    for(int i=0;i<=n;i++) 
	{
		pre[i]=i;
		r[i]=0;	
	}
}
int find(int x)
{
    if(x!=pre[x])
    {
        int t=pre[x];
        pre[x]=find(pre[x]);
        r[x]^=r[t];
    }
    return pre[x];
}
bool Union(int a,int b,int c)
{
    int ra=find(a),rb=find(b);
    if(ra==rb)//冲突 
    {
        if((r[a]^r[b])!=c) 
			return false;
        else 
			return true;
    }
    if(ra==n) 
		swap(ra,rb);  
    pre[ra]=rb;
    r[ra]=r[a]^r[b]^c;
    return true;
}
int Query()
{
    bool vis[N];
	memset(vis,false,sizeof(vis));
    int ans=0;
    for(int i=0;i<k;i++)
    {
        if(vis[i])
			continue;
        int cnt=0;
        int root=find(num[i]);//根 
        for(int j=i;j<k;j++)
        {
            if(!vis[j]&&find(num[j])==root)//j没有访问过 且在一个集合 
            {
                cnt++;
                vis[j]=true;
                ans^=r[num[j]];
            }
        }
        if(root!=n&&cnt&1) return -1;
    }
    return ans;
}
int main()
{
    int t=0;
   // freopen("test.txt","r",stdin);
    while(scanf("%d%d",&n,&q),n)
    {
        printf("Case %d:\n",++t);
        init();
        bool error=false;
        int fact=0;
        while(q--)
        {
            scanf("%s",ope);
            if(ope[0]=='I')
            {
                getchar();
				gets(ope);
				fact++;
                int space=0,u,v,w;
                for(int i=0;i<strlen(ope);i++) //检查有几个空格 
					space=space+(ope[i]==' '); 
                if(space==1) //一个空格表示2个输入
				{
					sscanf(ope,"%d%d",&u,&w);
					v=n;
				}
                else 
					sscanf(ope,"%d%d%d",&u,&v,&w);
                if(error) 
					continue;
                if(!Union(u,v,w))//冲突 
				{
					printf("The first %d facts are conflicting.\n",fact);
					error=true;
				}
            }
            else
            {
                scanf("%d",&k);
                for(int i=0;i<k;i++)
					scanf("%d",&num[i]);
                if(error) 
					continue;
                int ans=Query();
                if(ans==-1) 
					puts("I don't know.");
                else 
					printf("%d\n",ans);
            }
        }
        puts("");
    }
    return 0;
}