AT_agc016_d

算是第一次独立想出这样难度的题。

首先考虑手玩一下“变成整个序列的异或和”这个操作。发现如果一开始对 $i$ 位置进行操作，记录一个值为原来所有的 $a_i$ 中，现在不在 $a$ 中的 $a_i=x$，则以后：

• 如果对 $j(j\not=i)$ 操作，则 $a_j\to a_i,x\to a_j$

• 如果对 $i$ 进行操作，则 $a_i\to x$。

然后考虑转换一下问题，就是一开始先花一步选一个位置，把它变成特殊位置，然后每次操作可以选一个位置和特殊位置上的数互换，最后再用一步把特殊位置变回来，求最少需要多少次操作。

这个问题怎么解决呢？一开始考虑这会形成若干个环，但是如果出现重复值会假。然后发现，如果设 $i$ 为特殊位置，然后令 $j$ 和它交换，则特殊位置的值会变成 $a_j$，并且如果交换后 $a_j=b_j$ 则以后不会再动 $j$。

这启发我们让 $a_j$ 向 $b_j$ 连边，每次让特殊位置的 $a_i$ 找到一个 $b_j=a_i$，然后将这位解决，并修改 $x$ 的值为 $a_j$。因此可以发现，此时原问题的限制就变成，我们需要将每条边恰好经过一次。

这是什么？欧拉路问题，并且容易发现是回路。再进一步思考，由于有解时每个点 $in_i=out_i$，所以每个联通块一定都有在块内的欧拉回路。

对于多个连通块呢？发现每多一个连通块，就要额外多耗费一次去先进入这个连通块。于是设联通块数量为 $c$，则答案至多为 $n+c$。并查集维护。

其实到这里这题的主题部分已经解决了，但是为什么说至多呢？因为这题还是有很多细节的。

• 首先，如果可重集 $a$ 不等于可重集 $b$，则如果 $b$ 只比 $a$ 多一个数，且多的数为 $\bigoplus_i a_i$，则是有解的，具体就是把 $a$ 中多出来的变成这个，同时答案也要变化。

• 其次，设置和取消特殊位置的两步，如果有一个 $a_i=\bigoplus_ia_i$，则可以省去其中一步。

• 再者，还要特判有 $a_i=b_i$，可以直接省略这一位。同时，还要特判全相等/只有一个位置不等的情况。

• 其他还有较多细节，不一一展开讲，具体可以参考代码。但是由于我感觉这题数据不算特别强，所以欢迎 hack。

总的来说，这是一道完美地融合了两个非常巧妙的思维的神题。虽然比较粪的实现可能给我带来了一定困扰，但是不得不说我还是非常喜欢这一题的。

code：

int n,m,a[N],b[N],d[N],c[N],f[N],g[N];
struct DSU{
	int fa[N],siz[N];
	void init(){
		rep(i,1,m){
			fa[i]=i,siz[i]=1;
		}
	}
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	il void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y){
			return;
		}
		siz[y]+=siz[x],fa[x]=y;
	}
}D;
void Yorushika(){
	scanf("%d",&n);
	int s=0;
	rep(i,1,n){
		scanf("%d",&a[i]);
		s^=a[i],d[i]=a[i];
	}
	int ans=n;
	rep(i,1,n){
		scanf("%d",&b[i]);
		if(a[i]==b[i]){
			a[i]=b[i]=-1;
			ans--;
		}
		d[i+n]=b[i];
	}
	if(!ans){
		puts("0");
		return;
	}
	if(ans==1){
		rep(i,1,n){
			if(~a[i]){
				if(b[i]==s){
					puts("1");
				}else{
					puts("-1");
				}
				return;
			}
		}
	}
	sort(d+1,d+n+n+1),m=unique(d+1,d+n+n+1)-d-1;
	rep(i,1,n){
		f[i]=lower_bound(d+1,d+m+1,a[i])-d;
		g[i]=lower_bound(d+1,d+m+1,b[i])-d;
		c[f[i]]++,c[g[i]]--;
	}
	int sum=0;
	rep(i,1,m){
		sum+=abs(c[i]);
	}
	if(sum>2){
		puts("-1");
		return;
	}
	if(!sum){
		if(*lower_bound(d+1,d+m+1,s)==s){
			ans--;
		}
	}else{
		ans--;
		rep(i,1,m){
			if(c[i]==-1){
				if(d[i]!=s){
					puts("-1");
					return;
				}
			}
		}
		rep(i,1,m){
			if(c[i]==1){
				rep(j,1,n){
					if(a[j]==d[i]&&b[j]==s){
						a[j]=s,f[j]=-1;
						goto END;
					}
				}
				rep(j,1,n){
					if(a[j]==d[i]){
						a[j]=s,f[j]=lower_bound(d+1,d+m+1,a[j])-d;
						goto END;
					}
				}
			}
		}
	}
	END:
	D.init();
	rep(i,1,n){
		if(~f[i]){
			D.merge(f[i],g[i]);
		}
	}
	rep(i,1,m){
		if(D.fa[i]==i&&D.siz[i]!=1){
			ans++;
		}
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}