{"raw_statement":[{"iden":"background","content":"D_T_ : D_tt : ddT_ : ddtt = 9 : 3 : 3 : 1."},{"iden":"statement","content":"给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 `D` 或 `d`。\n\n定义无序点对 $(x, y)$ 是「[铁的](https://loj.ac/p/3398)」，当且仅当 $x \\neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。\n\n小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。\n\n注意：\n\n- 简单路径定义为不经过重复 **节点** 的路径。\n- 保证图无自环，可能有重边。"},{"iden":"input","content":"第一行一个整数 $S$，表示该测试点的 Subtask 编号。\n\n第二行两个整数 $n, m$。\n\n接下来 $m$ 行，每行两个整数 $x, y$ 以及字母 $c$，表示一条连接 $x, y$ 且标有 $c$ 的无向边。"},{"iden":"output","content":"一行一个整数表示答案。"},{"iden":"note","content":"**「数据范围与约定」**\n\n**本题采用捆绑测试**。\n\n- Subtask #1（6 points）：$n \\leq 8$，$m \\leq 20$。\n- Subtask #2（16 points）：$n\\leq 15$，$m\\leq 822$。依赖 Subtask #1。\n- Subtask #3（17 points）：$m = n - 1$。\n- Subtask #4（18 points）：$m = n$。\n- Subtask #5（19 points）：$n\\leq 1064$，$m\\leq 10 ^ 4$。依赖 Subtask #2。\n- Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。\n\n对于 $100\\%$ 的数据：\n\n- $2\\leq n \\leq 4\\times 10 ^ 5$，$n - 1\\leq m\\leq  10 ^ 6$。\n- $1\\leq x, y\\leq n$。\n- $c\\in \\{\\texttt{D}, \\texttt{d}\\}$。\n- 保证图无自环，可能有重边。\n\n**「帮助与提示」**\n\n请注意 IO 优化。\n\n**「题目来源」**\n\n- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) E\n- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。\n- Tester：[asmend](https://www.luogu.com.cn/user/21658)。"}],"translated_statement":null,"sample_group":[["0\n8 13\n1 2 d\n1 3 d\n2 3 d\n3 4 d\n3 5 D\n4 5 d\n4 6 d\n5 6 D\n6 7 d\n6 8 d\n6 8 D\n6 8 D\n7 8 d","24"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}