P8456 "SWTR-8" Subway

D\_T\_ : D\_tt : ddT\_ : ddtt = 9 : 3 : 3 : 1.

You are given an undirected connected graph with $n$ vertices and $m$ edges. Each edge is labeled `D` or `d`. Define an unordered pair of vertices $(x, y)$ to be "[Iron](https://loj.ac/p/3398)" if and only if $x \neq y$ and there exists a simple path between $x$ and $y$ on which both `D` and `d` appear. A knows the importance of the law of independent assortment DdTt, so he asks you to count such vertex pairs. Notes: - A simple path is a path that does not pass through any repeated **vertex**. - The graph is guaranteed to have no self-loops, and it may contain multiple edges.

The first line contains an integer $S$, indicating the Subtask ID of this test point. The second line contains two integers $n, m$. The next $m$ lines each contain two integers $x, y$ and a letter $c$, meaning there is an undirected edge connecting $x$ and $y$ labeled $c$.

Output one integer in one line, representing the answer.

**Constraints and Conventions** **This problem uses bundled testdata**. - Subtask #1 (6 points): $n \leq 8$, $m \leq 20$. - Subtask #2 (16 points): $n \leq 15$, $m \leq 822$. Depends on 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$. Depends on Subtask #2. - Subtask #6 (24 points): No special limits. Depends on Subtask #3, #4, #5. For $100\%$ of the data: - $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}\}$. - The graph is guaranteed to have no self-loops, and it may contain multiple edges. **Help and Tips** Please pay attention to I/O optimization. **Source** - [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). Translated by ChatGPT 5