提交时间:2024-11-06 09:21:31

运行 ID: 34340

#include<bits/stdc++.h> using namespace std; const int N=5e5+10; int n,fa[N],rk[N],cnt; int find_root(int u){ // cout<<u<<" "<<fa[u]<<endl; if(fa[u]==u)return u; return fa[u]=find_root(fa[u]); } void merge(int u,int v){ if(fa[u]==fa[v])return; // cout<<"!"<<u<<" "<<v<<endl; int x=find_root(u),y=find_root(v); // cout<<x<<" "<<y<<endl; if(rk[x]>rk[y]){fa[y]=x;rk[x]++;} else {fa[x]=y;rk[y]++;} return; } int a[N],b[N],t[N]; map<int,int>mp; int main(){ // freopen("xor.in","r",stdin); // freopen("xor.out","w",stdout); cin>>n; for(int i=1;i<=n+1;i++)fa[i]=i; for(int i=1;i<=n;i++){cin>>a[i];a[n+1]^=a[i];t[i]=a[i];}t[n+1]=a[n+1]; for(int i=1;i<=n;i++){cin>>b[i];b[n+1]^=b[i];t[i+n+1]=b[i];}t[2*n+2]=b[n+1]; sort(t+1,t+2*n+3); int ct=0; for(int i=1;i<=2* n+2;i++){ if(t[i]!=t[i-1]||i==1)mp[t[i]]=++ct; // cout<<t[i]<<" "<<ct<<endl; } for(int i=1;i<=n+1;i++){ if(i==n+1){ if(fa[mp[a[i]]]!=mp[a[i]]||rk[mp[a[i]]]>0)continue; } if(a[i]!=b[i]){ merge(mp[a[i]],mp[b[i]]);cnt++; } } // cout<<cnt<<endl; for(int i=1;i<=n+1;i++){ if(fa[mp[a[i]]]==mp[a[i]]&&(a[i]!=b[i])){cnt++;} // cout<<i<<" "<<fa[i]<<" "<<a[i]<<" "<<b[i]<<" "<<cnt<<endl; }//cout<<endl; // cout<<cnt<<endl; cnt--; sort(a+1,a+n+2);sort(b+1,b+n+2); // for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl; for(int i=1;i<=n+1;i++){ if(a[i]!=b[i]){ cout<<-1<<endl;return 0; } } cout<<cnt<<endl; return 0; }