P7323 [WC2021] 括号路径

给定一张 $n$ 个点 $2 m$ 条边的有向图，图中的每条边上都有一个标记，代表一个左括号或者右括号。共有 $k$ 种不同的括号类型，即图中可能有 $2 k$ 种不同的标记。点、边、括号种类均从 $1$ 开始编号。 图中的每条边都会和另一条边成对出现。更具体地，若图中存在一条标有第 $w$ 种括号的左括号的边 $(u, v)$，则图中一定存在一条标有第 $w$ 种括号的右括号的边 $(v, u)$。同样地，图中每条标有右括号的边将对应着一条反方向的标有同类型左括号的边。 现在请你求出，图中共有多少个点对 $(x, y)$（$1 \le x < y \le n$）满足：图中存在一条从 $x$ 出发到达 $y$ 的路径，且按经过顺序将路径各条边上的标记拼接得到的字符串是一个合法的括号序列。

无

无

**【样例解释 #1】** 符合条件的点对及其对应的路径为： $(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$。 **【数据范围】** 对于所有测试点：$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$。 每个测试点的具体限制见下表： | 测试点编号 | $n =$ | $m \le$ | $k \le$ | 特殊限制 | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 4$ | $4$ | $5$ | $2$ | 无 | | $5 \sim 8$ | $8$ | $10$ | $2$ | 无 | | $9 \sim 12$ | $3000$ | $6000$ | $1$ | 无 | | $13 \sim 16$ | $3000$ | $n - 1$ | $n$ | 不存在仅由带左括号标记的边构成的环 | | $17 \sim 20$ | $3 \times {10}^5$ | $n - 1$ | $n$ | 不存在仅由带左括号标记的边构成的环 | | $21 \sim 25$ | $3 \times {10}^5$ | $6 \times {10}^5$ | $n$ | 无 |