「SWTR-8」地地铁铁

D_T_ : D_tt : ddT_ : ddtt = 9 : 3 : 3 : 1.

给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 `D` 或 `d`。 定义无序点对 $(x, y)$ 是「[铁的](https://loj.ac/p/3398)」，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。 小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。 注意： - 简单路径定义为不经过重复 **节点** 的路径。 - 保证图无自环，可能有重边。

第一行一个整数 $S$，表示该测试点的 Subtask 编号。 第二行两个整数 $n, m$。 接下来 $m$ 行，每行两个整数 $x, y$ 以及字母 $c$，表示一条连接 $x, y$ 且标有 $c$ 的无向边。

一行一个整数表示答案。

0
8 13
1 2 d
1 3 d
2 3 d
3 4 d
3 5 D
4 5 d
4 6 d
5 6 D
6 7 d
6 8 d
6 8 D
6 8 D
7 8 d

24

**「数据范围与约定」** **本题采用捆绑测试**。 - Subtask #1（6 points）：$n \leq 8$，$m \leq 20$。 - Subtask #2（16 points）：$n\leq 15$，$m\leq 822$。依赖 Subtask #1。 - Subtask #3（17 points）：$m = n - 1$。 - Subtask #4（18 points）：$m = n$。 - Subtask #5（19 points）：$n\leq 1064$，$m\leq 10 ^ 4$。依赖 Subtask #2。 - Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。 对于 $100\%$ 的数据： - $2\leq n \leq 4\times 10 ^ 5$，$n - 1\leq m\leq 10 ^ 6$。 - $1\leq x, y\leq n$。 - $c\in \{\texttt{D}, \texttt{d}\}$。 - 保证图无自环，可能有重边。 **「帮助与提示」** 请注意 IO 优化。 **「题目来源」** - [Sweet Round 8](https://www.luogu.com.cn/contest/73382) E - Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。 - Tester：[asmend](https://www.luogu.com.cn/user/21658)。