rt，赛时写了一个一眼假的复杂度，大样例0.2s日过去了。洛谷上跑得飞快，70ms。我觉得能卡成 $O(nm\log m)$ 但是蒟蒻卡不来.jpg

#include <bits/stdc++.h>

#define rep(i, a, b) for (long long i = (a); i <= (b); i++)
#define _rep(i, a, b) for (long long i = (a); i >= (b); i--)

using namespace std;

#define int ll

typedef long long ll;
typedef pair <int, int> pii;

#define TRUE 1000001
#define FALSE 1000002
#define UNKNOWN 1000003

const int MAXN = 5e5 + 5;
int c, T, n, m;
vector <pii> rel[MAXN];
int fn[MAXN], v[MAXN];
vector <pii> G[MAXN];

int nxt(int val) {
    if (val == TRUE) return FALSE;
    if (val == FALSE) return TRUE;
    if (val == UNKNOWN) return UNKNOWN;
    return -val;
}

bool vis[MAXN], vise[MAXN];
void dfs(int val, int u) {
    if (vis[u]) {
        if (val == v[u]) return;
        else v[u] = UNKNOWN;
        return;
    }
    vis[u] = 1;
    v[u] = val;
    for (auto x : G[u]) {
        int v = x.first;
        int k = x.second;
        if (~k) dfs(val, v);
        else dfs(nxt(val), v);
    }
}

void expand(int u) {
    if (vise[u]) return;
    vise[u] = 1;
    v[u] = UNKNOWN;
    for (auto x : G[u]) {
        int v = x.first;
        expand(v);
    }
}

int read() {
    int w = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        w = (w << 3) + (w << 1) + (c ^ 48);
        c = getchar();
    }
    return w * f;
}

signed main() {
#ifndef LOCAL
    freopen("tribool.in", "r", stdin);
    freopen("tribool.out", "w", stdout);
#endif
    c = read(), T = read();
    while (T --> 0) {
        n = read(), m = read();
        memset(vis, 0, sizeof vis);
        memset(fn, 0, sizeof fn);
        memset(v, 0, sizeof v);
        memset(vise, 0, sizeof vise);
        rep (i, 1, n) rel[i].clear(), G[i].clear(), v[i] = 0, rel[i].emplace_back(make_pair(0ll, i));
        rep (i, 1, m) {
            char op = getchar();
            while (op == '\n' || op == '\r' || op == ' ') op = getchar();
            if (op == '+' || op == '-') {
                int u, v;
                u = read(), v = read();
                rel[u].emplace_back(make_pair(i, (op == '+' ? 1ll : -1ll) * v));
            }
            else {
                int u = read();
                if (op == 'U') rel[u].emplace_back(make_pair(i, UNKNOWN));
                else if (op == 'T') rel[u].emplace_back(make_pair(i, TRUE));
                else rel[u].emplace_back(make_pair(i, FALSE));
            }
        }
        rep (i, 1, n) {
            int nw = rel[i][rel[i].size() - 1].second;
            int ops = rel[i][rel[i].size() - 1].first;
            int flg = 0;
            while (nw <= n && ops > 0) {
                flg = (nw < 0);
                nw = abs(nw);
                auto tmp = lower_bound(rel[nw].begin(), rel[nw].end(), make_pair(ops, -10000000ll));
                tmp--;
                auto val = *tmp;
                if (flg) nw = nxt(val.second);
                else nw = val.second;
                ops = val.first;
            }
            fn[i] = nw;
        }
        rep (i, 1, n) {
            if (fn[i] > 1e6) continue;
            G[abs(fn[i])].emplace_back(make_pair(i, (fn[i] > 0 ? 1ll : -1ll)));
            G[i].emplace_back(make_pair(abs(fn[i]), (fn[i] > 0 ? 1ll : -1ll)));
        }
        rep (i, 1, n) {
            if (fn[i] > 1e6) {
                v[i] = fn[i];
                dfs(v[i], i);
            }
            if (fn[i] == -i) {
                v[i] = UNKNOWN;
                dfs(v[i], i);
            }
            if (fn[i] == i) {
                v[i] = TRUE;
                dfs(v[i], i);
            }
        }
        rep (i, 1, n) {
            if (!v[i]) dfs(TRUE, i);
        }
        rep (i, 1, n) {
            if (!vise[i] && v[i] == UNKNOWN) expand(i);
        }
        int ans = 0;
        rep (i, 1, n) {
            if (v[i] == UNKNOWN) ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}