题意：
有n个人，m对关系，每对关系u , v表示u说v是s。每个人有两个身份，船员和冒名者，船员的话全部为真话，冒名者的话全部为假话。问最多有多少个冒名者。
思路：
经典并查集(不是
扩展域并查集，x表示这个人是船员，x + n表示这个人是冒名者。
推理一下关系会发现，如果s为船员c r e w m a t e的话，两者的身份是相同的；否则，两者的身份是不同的，正常合并就可以。
用s i z [ i ]维护i在的集合里冒名者的人数。
最后，如果x和x + n在同一个集合里，说明出现了矛盾。
不然就遍历[ 1 , 2 ∗ n ],对于每个集合取是船员和是冒名者的s i z的最大值。
由于在船员跟冒名者的身份都加了一次，所以最后总和要/ 2
代码：
// Problem: D. The Number of Imposters // Contest: Codeforces - Codeforces Round #747 (Div. 2) // URL: https://codeforces.com/contest/1594/problem/D // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll 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;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; int root[maxn],siz[maxn],n,m; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } void Union(int u,int v){ int fu=Find(u),fv=Find(v); if(fu!=fv){ root[fu]=fv; siz[fv]+=siz[fu]; siz[fu]=0; } } int main(){ int _=read; while(_--){ n=read,m=read; rep(i,1,2*n){ root[i]=i; if(i<=n) siz[i]=0; else siz[i]=1; } while(m--){ int u=read,v=read; string s;cin>>s; if(s[0]=='i'){ Union(u,v+n); //Union(u+n,v); Union(v,u+n); } else{ Union(u,v);Union(u+n,v+n); } } // rep(i,1,n){ // cout<<Find(i)<<" "<<siz[Find(i)]<<endl; // } int ans=0; for(int i=1;i<=2*n;i++){ int fu=Find(i),fv; if(i<=n) fv=Find(i+n); else fv=Find(i-n); if(fu==fv) ans=-1; if(i==fu&&ans!=-1) ans=ans+max(siz[fu],siz[fv]); } if(ans!=-1) cout<<ans/2<<endl; else cout<<ans<<endl; } return 0; }
