Background

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

Problem Description

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" 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.

Input Format

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 Format

Output one integer in one line, representing the answer.

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

Hint

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 E.
• Idea & Solution: Alex_Wei.
• Tester: asmend.

Translated by ChatGPT 5