rt。用带权并查集维护。

#include <bits/stdc++.h>
typedef long long ll;
#define int long long

const int N = 2e5 + 10; 

// lst[i] 表示 i 元素的最终状态的节点
// 每个元素 i 的初始状态节点为 i
// T = n + m + 1
// U = n + m + 2
// 权值为 1 时表相同，0 时表相反

int n, m, lst[N], anc[N];

int val[N]; // val[i] 表示节点 i 到其父亲节点的边权，路径压缩后表示到根节点的边权

int find(int x) {
	if (x != anc[x]) {
		int fa = anc[x];
		anc[x] = find(fa);
		(val[x] += val[fa]) &= 1; 	
	}
	return anc[x]; 
}

int path_len(int u, int v) {
	int ancu = find(u), ancv = find(v);
	if (ancu != ancv) return -1;
	return val[u] + val[v] & 1;
}

void merge(int u, int v, int d) {
	int ancu = find(u), ancv = find(v);
	if (ancu != ancv) { // ancu --> ancv
		val[ancv] = d + 2 - (val[u] + val[v] & 1) & 1;
		anc[ancv] = ancu;
	}
	return void();
}

std::vector <int> vec; 

void solve() {
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i) lst[i] = i;
	int _idx = n + m + 2;
	for (int i = 1; i <= _idx; ++ i) anc[i] = i, val[i] = 0; 
	int idx = n; 
	while (m --> 0) {
		char op; std::cin >> op;
		if (op == 'T' || op == 'F' || op == 'U') {
			int id; std::cin >> id;
			lst[id] = ++ idx;
			if (op == 'T') merge(idx, _idx - 1, 0);
			if (op == 'F') merge(idx, _idx - 1, 1);
			if (op == 'U') merge(idx, _idx, 0);
		}  
		else {
			int i, j; std::cin >> i >> j;
			if (op == '+') merge(idx + 1, lst[j], 0);
			if (op == '-') merge(idx + 1, lst[j], 1); 
			lst[i] = ++ idx;
		}
	}
	int cnt = 0; 
	vec.clear(); 
	for (int i = 1; i <= n; ++ i) if (path_len(lst[i], i) == 1) vec.push_back(i);
	for (auto i : vec) merge(i, _idx, 0);  
//	for (int i = 1; i <= n; ++ i) std::cout << anc[i] << " "; std::cout << "\n"; 
	for (int i = 1; i <= n; ++ i) merge(i, lst[i], 0);
//	std::cout << fU << "\n"; 
	for (int i = 1; i <= n; ++ i)
		if (find(i) == find(_idx)) ++ cnt;
	
//	for (int i = 1; i <= n; ++ i) std::cout << anc[i] << " "; std::cout << "\n"; 
	
	std::cout << cnt << "\n";
	return void(); 
}

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int type, _; std::cin >> type >> _;
	while (_ --> 0) {
		solve(); 
	}

	return 0;
}