Given a directed graph with $n$ vertices and $2m$ edges, each edge in the graph has a label representing either an opening bracket or a closing bracket. There are $k$ different types of brackets, meaning there are $2k$ possible distinct labels in the graph. Vertices, edges, and bracket types are all numbered starting from 1.
Every edge in the graph appears in a pair with another edge. Specifically, if there exists an edge $(u, v)$ labeled with the $w$-th type of opening bracket, then there must exist an edge $(v, u)$ labeled with the $w$-th type of closing bracket. Similarly, every edge labeled with a closing bracket corresponds to an edge in the opposite direction labeled with the same type of opening bracket.
Find the number of pairs of vertices $(x, y)$ ($1 \le x < y \le n$) such that there exists a path from $x$ to $y$ in the graph, and the string formed by concatenating the labels of the edges along the path in order is a valid bracket sequence.
Input
The input is read from the file bracket.in.
The first line contains three integers $n, m, k$, representing the number of vertices, the number of edge pairs, and the number of bracket types, respectively.
The next $m$ lines each contain three integers $u, v, w$, representing a directed edge from $u$ to $v$ labeled with the $w$-th type of opening bracket, and a directed edge from $v$ to $u$ labeled with the $w$-th type of closing bracket.
In the given graph, there may be multiple directed edges between any two distinct vertices, but there are no self-loops (i.e., $u \neq v$).
Output
The output is written to the file bracket.out.
Output a single integer representing the number of vertex pairs that satisfy the condition.
Examples
Input 1
4 5 1 4 3 1 4 2 1 1 3 1 2 1 1
Output 1
3
Note 1
The valid vertex pairs and their corresponding paths are: $(1, 2): 1 \to 3 \to 4 \to 1 \to 2$. $(1, 4): 1 \to 3 \to 4$. $(2, 4): 2 \to 1 \to 4$.
Input 2
6 8 2 6 1 2 3 5 1 1 2 2 5 1 2 3 6 2 4 3 1 6 2 2 3 2 1
Output 2
10
Constraints
For all test cases: $1 \le n \le 3 \times 10^5$, $1 \le m \le 6 \times 10^5$, $1 \le k, u, v \le n$, $1 \le w \le k$.
The specific constraints for each test case are shown in the table below:
| Test Case ID | $n =$ | $m \le$ | $k \le$ | Special Constraints |
|---|---|---|---|---|
| $1 \sim 4$ | $4$ | $5$ | $2$ | None |
| $5 \sim 8$ | $8$ | $10$ | $2$ | None |
| $9 \sim 12$ | $3000$ | $6000$ | $1$ | None |
| $13 \sim 16$ | $3 \times 10^5$ | $n - 1$ | $n$ | No cycles consisting only of edges labeled with opening brackets |
| $17 \sim 20$ | $3 \times 10^5$ | $6 \times 10^5$ | $n$ | No cycles consisting only of edges labeled with opening brackets |
| $21 \sim 25$ | $3 \times 10^5$ | $6 \times 10^5$ | $n$ | None |