背景

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

题目描述

给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 D 或 d。

定义无序点对 $(x, y)$ 是「铁的」，当且仅当 $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 E
• Idea & Solution：Alex_Wei。
• Tester：asmend。