代码：

#include <cassert>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <tuple>
#include <vector>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 1e6 + 5;

int n, m, t, cnt;
i64 ans;
int dfn[kMaxN], low[kMaxN], col[kMaxN], ss[kMaxN], fa[kMaxN], sz[kMaxN], q[kMaxN];
bool in[kMaxN], vis[kMaxN];
std::vector<int> T[kMaxN];
std::vector<std::tuple<int, int, int>> G[kMaxN];

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void unionn(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) fa[fx] = fy, sz[fy] += sz[fx];
}

void tarjan(int u, int lst) {
  static int cnt = 0;
  static std::stack<int> stk;
  dfn[u] = low[u] = ++cnt;
  stk.emplace(u);
  for (auto [v, c, id] : G[u]) {
    if (!dfn[v]) {
      tarjan(v, id);
      low[u] = std::min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        ++t;
        while (!stk.empty()) {
          int k = stk.top();
          stk.pop();
          T[t].emplace_back(k), T[k].emplace_back(t);
          if (k == v) break;
        }
        T[t].emplace_back(u), T[u].emplace_back(t);
      }
    } else if (id != lst) {
      low[u] = std::min(low[u], dfn[v]);
    }
  }
}

void bfs(int id) {
  for (auto x : T[id]) {
    in[x] = 1;
    ss[x] = 0;
  }
  int h = 1, t = 0;
  int s = 0;
  q[++t] = T[id][0], vis[T[id][0]] = 1;
  while (h <= t) {
    int u = q[h++];
    for (auto [v, c, id] : G[u]) {
      if (!in[v]) continue;
      s |= (1 << c), ss[u] |= (1 << c), ss[v] |= (1 << c);
      if (!vis[v]) q[++t] = v, vis[v] = 1;
    }
  }
  int cnt = 0;
  for (auto x : T[id]) {
    in[x] = vis[x] = 0;
    cnt += (ss[x] == 3);
    ss[x] = 0;
  }
  if (cnt == 2) --ans;
  if (s == 3) s = 0;
  else if (s == 0) s = 3;
  col[id] = s;
}

void dickdreamer() {
  std::cin >> n >> m;
  ans = (i64)n * (n - 1) / 2;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::string c;
    std::cin >> u >> v >> c;
    G[u].emplace_back(v, c[0] == 'd', i), G[v].emplace_back(u, c[0] == 'd', i);
  }
  t = n;
  for (int i = 1; i <= n; ++i)
    if (!dfn[i])
      tarjan(i, 0);
  // std::cerr << "!!!\n";
  // for (int i = n + 1; i <= t; ++i)
  //   std::cerr << T[i].size() << '\n';
  for (int i = n + 1; i <= t; ++i)
    bfs(i);
  // std::cerr << "???\n";
  for (int i = 1; i <= t; ++i) {
    fa[i] = i;
    sz[i] = (i <= n);
  }
  for (int i = n + 1; i <= t; ++i)
    if (col[i] == 1)
      for (auto j : T[i])
        unionn(i, j);
  for (int i = 1; i <= t; ++i)
    if (find(i) == i)
      ans -= (i64)sz[i] * (sz[i] - 1) / 2;
  for (int i = 1; i <= t; ++i) {
    fa[i] = i;
    sz[i] = (i <= n);
  }
  for (int i = n + 1; i <= t; ++i)
    if (col[i] == 2)
      for (auto j : T[i])
        unionn(i, j);
  for (int i = 1; i <= t; ++i)
    if (find(i) == i)
      ans -= (i64)sz[i] * (sz[i] - 1) / 2;  
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1, S;
  // std::cin >> T;
  std::cin >> S;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

里面的

void bfs(int id) {
  for (auto x : T[id]) {
    in[x] = 1;
    ss[x] = 0;
  }
  int h = 1, t = 0;
  int s = 0;
  q[++t] = T[id][0], vis[T[id][0]] = 1;
  while (h <= t) {
    int u = q[h++];
    for (auto [v, c, id] : G[u]) {
      if (!in[v]) continue;
      s |= (1 << c), ss[u] |= (1 << c), ss[v] |= (1 << c);
      if (!vis[v]) q[++t] = v, vis[v] = 1;
    }
  }
  int cnt = 0;
  for (auto x : T[id]) {
    in[x] = vis[x] = 0;
    cnt += (ss[x] == 3);
    ss[x] = 0;
  }
  if (cnt == 2) --ans;
  if (s == 3) s = 0;
  else if (s == 0) s = 3;
  col[id] = s;
}

这个玩意为啥会 T 啊！！！

它不是线性的吗