思路:与https://www.bilibili.com/video/BV1SC4y1m7zD/?spm_id_from=333.337.search-card.all.click&vd_source=c42ae4e60815003575acd88813c316f6 以及那个二分图做法的题解 类似

确定了T/F/U的连通块只要有U全是U；不确定的连通块不是二分图（矛盾）就全是U

#include<bits/stdc++.h>
#define add(x,y,w) g[x].push_back({y,w})
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e5+5;
struct Edge {
	int v, w;//w: 0- 1+
};
int n, m, C, t;
vector<Edge> g[N];
int ans, cnt, color[N],fa[N];//fa[x]:最终与x相关点
bool vis[N];//标记确定有色点
bool v[N];//标记已访问无色点
bool flagu;
void Init() {
	ans = cnt = 0;
	flagu=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	for (int i = 0; i < N; i++) vector<Edge>().swap(g[i]);
	memset(vis, 0, sizeof(vis));
	memset(color, 0, sizeof(color));
	memset(v,0,sizeof(v));//debug:多测不清空...
}

void Search(int x) {
	if(color[x]==3) flagu=1;//连通块内有U，则全是U
	vis[x] = 1;
	cnt++;
	for (auto e : g[x])
		if (!vis[e.v]) Search(e.v);
}

void getsize(int x)
{
	v[x] = 1;
	cnt++;
	for (auto e : g[x])
		if (!v[e.v]) getsize(e.v);
}
bool dfs(int x, int c) { //是否不含U的二分图
	color[x] = c;
	//cnt++; debug:判二分图不能遍历到所有点
	//vis[x] = 1;
	//if(color[x]==3) return 0;//特判孤立点U
	for (auto e : g[x]) {
		int y = e.v, w = e.w;
		/*	if (color[y] == 3) { //连通块被U污染
		cnt--;
		return 0;
		}*/
		if(vis[y]) continue;
		if (!color[y]) { //未被染色
			if (w == 1&&!dfs(y,c)) return 0;//return dfs(y, c);debug:二分图一个节点里return 1不能代表全部都是return 1!!!!!
			else if(w==0&&!dfs(y, 3 - c)) return 0;
		} else if (color[y] == c && w == 0) {/*color[y]=3;*/return 0;}
		else if (color[y] == 3 - c && w == 1) {return 0;}
		//else if(color[y]==3) return 0; 	 	
	}
	return 1;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> C >> t;
	while (t--) {
		cin >> n >> m;
		Init();
		while (m--) {
			char op;
			int x = 0, y = 0;
			cin >> op >> x;
			switch (op) {
				
				case 'T': {
					color[x] = 1;
					break;
				}
				case 'F': {
					color[x] = 2;
					break;
				}
				case 'U': {
					color[x] = 3;
					break;
				}
				case '+': {
					cin >> y;
					fa[x]=fa[y];
					color[x]=0;//debug：覆盖后就不是有色点！
					//add(y, x, 1);
					//add(x, y, 1); //debug:二分图判的是无向图！
					break;
				}
				default: {
					cin >> y;
					fa[x]=-fa[y];
					color[x]=0;
					//add(y, x, 0);
					//add(x, y, 0);
				}
			}
		}
		//for(int i=1;i<=n;i++){
		//	cout<<fa[i]<<' ';
		//}
		//if(t!=2) continue;
		for(int i=1;i<=n;i++)
		{
			if(!color[i])
			{
				//cout<<i<<' '<<fa[i]<<'\n';
				add(i,abs(fa[i]),fa[i]>0?1:0);
				add(abs(fa[i]),i,fa[i]>0?1:0);
			}	
		}	
	/*	for (int i = 1; i <= n; i++) {//有色点前驱染色
		if (!color[i])//如果没被染色
		for (auto e : g[i])
		if (color[e.v])
		color[i] = e.w ? color[e.v] : (3 - color[e.v]);
		}*/
		for (int i = 1; i <= n; i++) {//有色连通块排除
			cnt = 0;flagu=0;
			if (!vis[i] && color[i]) Search(i);
			if (flagu)	ans += cnt; //含U的连通块
			//cout<<cnt<<endl;
			//else if (color[i] == 3 && !g[i].size()) ans++;//特判孤立U点
		}
		for (int i = 1; i <= n; i++) {//无色连通块判二分图
			cnt = 0;
			if(!vis[i]&&!v[i])//无色 未被判过二分图
			{
				getsize(i);//计算连通块大小
				if (!dfs(i, 1)) /*cout<<cnt<<endl,*/ans += cnt;//非二分图，全是U
				
			}
		}
		cout << ans << '\n';
		//cout<<endl<<endl<<endl;
	}
	return 0;
}