Description

Given a directed graph with $n$ vertices and $2 m$ edges, each edge has a label, which is either a left bracket or a right bracket. There are $k$ different bracket types, so the graph may contain $2 k$ different labels. Vertices, edges, and bracket types are all numbered starting from $1$.

Each edge in the graph appears in a paired way with another edge. More specifically, if there is an edge $(u, v)$ labeled with the left bracket of type $w$, then there must be an edge $(v, u)$ labeled with the right bracket of the same type $w$. Similarly, every edge labeled with a right bracket corresponds to an opposite-direction edge labeled with the left bracket of the same type.

Now you need to compute how many pairs of vertices $(x, y)$ ($1 \le x < y \le n$) satisfy the following: there exists a path from $x$ to $y$ in the graph such that, if you concatenate the labels of the edges along the path in the order they are traversed, the resulting string is a valid bracket sequence.

Input Format

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.

The next $m$ lines each contain three integers $u, v, w$, indicating: a directed edge from $u$ to $v$ labeled with the left bracket of type $w$; and a directed edge from $v$ to $u$ labeled with the right bracket of type $w$.

In the given graph, there may be multiple directed edges between any two different vertices, but there are no self-loops, i.e., $u \ne v$.

Output Format

Output a single integer in one line, the number of vertex pairs that satisfy the condition.

4 5 1
4 3 1
4 1 1
4 2 1
1 3 1
2 1 1

3

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

10

见附件中的 bracket/bracket3.in

见附件中的 bracket/bracket3.ans

见附件中的 bracket/bracket4.in

见附件中的 bracket/bracket4.ans

Hint

[Sample Explanation #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$.

[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 limits for each test case are shown in the table below:

Translated by ChatGPT 5