P7323 [WC2021] Bracket Path

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.

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 a single integer in one line, the number of vertex pairs that satisfy the condition.

**[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: | Test Case ID | $n =$ | $m \le$ | $k \le$ | Special Restriction | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 4$ | $4$ | $5$ | $2$ | None. | | $5 \sim 8$ | $8$ | $10$ | $2$ | None. | | $9 \sim 12$ | $3000$ | $6000$ | $1$ | None. | | $13 \sim 16$ | $3000$ | $n - 1$ | $n$ | There is no cycle consisting only of edges labeled with left brackets. | | $17 \sim 20$ | $3 \times {10}^5$ | $n - 1$ | $n$ | There is no cycle consisting only of edges labeled with left brackets. | | $21 \sim 25$ | $3 \times {10}^5$ | $6 \times {10}^5$ | $n$ | None. | Translated by ChatGPT 5