先算出每个数最后变成了啥，然后搜索算出哪些数必须是U/T/F。

对于剩下的部分，处理出必须相等的连通块，然后以这些连通块为点，必须为相反的连边，建一张新图。

对于新图中的每个连通块，如果有奇圈就必须全是U，否则就可以全是T/F。

然后我不会判奇圈，于是把它的BFS树建出来，有奇圈等价于有两端深度相同的边。

我也不知道我考场为什么把BFS树上的边存下来了。

考场代码，民间数据都过了。

#include<bits/stdc++.h>
using namespace std;
int read(){
	char c=getchar(); int a=0;
	while(c>'9'||c<'0') c=getchar();
	while(c<='9'&&c>='0'){
		a=a*10+(c-'0');
		c=getchar();
	}
	return a;
}
int ans,n,v[100010],iv[100010]; //x_i=i,U=-1,T=-2,F=-3 
void f1(){ //读入，并初步处理操作 
	int m; n=read(); m=read();
	for(int i=1;i<=n;++i){
		v[i]=i;
		iv[i]=0;
	}
	while(m--){
		char c=getchar();
		while(c==' '||c=='\n') c=getchar();
		if(c=='+'||c=='-'){
			int x,y; x=read(); y=read(); v[x]=v[y];
			if(c=='+') iv[x]=iv[y];
			else iv[x]=1-iv[y];
		}
		else{
			int x; x=read(); iv[x]=0;
			if(c=='U') v[x]=-1;
			else if(c=='T') v[x]=-2;
			else v[x]=-3;	
		} 
	}
} 
vector<int> gx[100010]; int fl[100010]; //无=0,U=1,TF=2 
void f2(){ //标记直接确定是UTF的
	queue<int> q;
	for(int i=1;i<=n;++i)
		if(v[i]>0) gx[v[i]].push_back(i);
		else{
			q.push(i);
			if(v[i]==-1) fl[i]=1;
			else fl[i]=2;
		}
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v:gx[u]){
			if(fl[v]!=0) continue;
			fl[v]=fl[u]; q.push(v);
		}
	}
	for(int i=1;i<=n;++i)
		if(fl[i]==1) ++ans;
}
//并查集
int fa[100010];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
} 
void merge(int x,int y){
	x=find(x); y=find(y);
	if(x!=y) fa[x]=y;
}
void init(){
	for(int i=1;i<=n;++i) fa[i]=i;
}
int ki[100010],ks[100010];
void f3(){ //建立+的连通块
	init();
	for(int i=1;i<=n;++i)
		if(fl[i]==0&&iv[i]==0) merge(i,v[i]);
	for(int i=1;i<=n;++i)
		if(fl[i]==0){
			ki[i]=find(i);
			ks[ki[i]]++;
		}
}
vector<int> ed[100010],dj[100010];
void f4(){ //建-的图，找连通块
	init();
	for(int i=1;i<=n;++i)
		if(fl[i]==0&&iv[i]==1){
			ed[ki[i]].push_back(ki[v[i]]); ed[ki[v[i]]].push_back(ki[i]);
			merge(ki[i],ki[v[i]]);
		}
	for(int i=1;i<=n;++i)
		dj[find(i)].push_back(i);
}
vector<int> e[100010]; int dep[100010]; 
void f5(vector<int> pt){ //建立BFS树，预处理dep 
	queue<int> q; q.push(pt[0]); dep[pt[0]]=1;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v:ed[u]){
			if(dep[v]) continue;
			dep[v]=dep[u]+1; q.push(v);
			e[u].push_back(v);
		}
	}
} 
bool f6(vector<int> pt){ //通过找是否有横插边判断是否为二分图 
	for(int u:pt)
		for(int v:ed[u])
			if(dep[u]==dep[v]) return 1;
	return 0;
}
void f7(){ //对每个连通块做 f5,f6，并求答案 
	for(int i=1;i<=n;++i){
		if(dj[i].empty()) continue;
		f5(dj[i]);
		if(!f6(dj[i])) continue;
		for(int x:dj[i]) ans+=ks[x];
	}
}
#define m(x) memset(x,0,sizeof(x))
#define c(x) for(int i=0;i<=100000;++i) x[i].clear()
void f0(){ //多测清零 
	ans=n=0; 
	m(v); m(iv); m(fl); c(gx); m(fa); m(ki); m(ks);
	c(ed); c(dj); c(e); m(dep);
}
#undef m
#undef c
int main(){
	freopen("tribool.in","r",stdin);
	freopen("tribool.out","w",stdout);
	int c,T; scanf("%d%d",&c,&T);
	while(T--){
		f0(); f1(); f2(); f3(); f4(); f7();
		printf("%d\n",ans); 
	}
	return 0;
}