Counting Iron Pairs

Given an undirected connected graph with n vertices and m edges. Each edge is labeled with either \(D\) or \(d\). An unordered pair of distinct vertices \((x,y)\) is called iron if and only if there exists a simple path (i.e. a path which does not repeat any vertex) between \(x\) and \(y\) that contains at least one edge labeled \(D\) and at least one edge labeled \(d\). Note that the graph contains no self‐loops but may have multiple edges.

Your task is to count the number of iron pairs \((x,y)\). Two vertices \(x\) and \(y\) (with \(x \neq y\)) form an iron pair if there exists at least one simple path from \(x\) to \(y\) that uses both kinds of edges.

Formally, let a simple path be denoted by \(x=v_0, v_1, \dots, v_k=y\) with all \(v_i\) distinct. Then \((x,y)\) is iron if and only if there exists some \(0 \le i < k\) for which the edge \(v_i v_{i+1}\) is labeled \(D\) and some \(0 \le j < k\) for which the edge \(v_j v_{j+1}\) is labeled \(d\).

Input Format: The input begins with two integers n and m on one line. Each of the following m lines contains two integers and a character: u v lab indicating there is an undirected edge between vertices u and v (1-indexed) with label lab (either D or d).

Note: It is guaranteed that the graph is connected.

inputFormat

The first line contains two integers n and m separated by spaces. The next m lines each contain two integers u and v and a character lab (either D or d), indicating an edge between vertices u and v with label lab.

outputFormat

Output a single integer denoting the number of iron pairs.

sample

2 1
1 2 D

0