AT_arc173_d [ARC173D] Bracket Walk

有一个包含 $N$ 个顶点和 $M$ 条边的有向图 $G$。顶点编号为 $1$ 到 $N$，每条边都被赋予了 `(` 或 `)` 的标签。第 $i$ 条边是从顶点 $u_i$ 指向顶点 $v_i$ 的有向边，标签为 $c_i$。该图中不存在重边和自环。 对于任意两个顶点 $s,t$，都存在从 $s$ 到 $t$ 的路径。 请判断在图 $G$ 上是否存在满足以下所有条件的**步行**： - 步行的起点和终点是同一个顶点。 - 对于 $i=1,2,\dots,M$，第 $i$ 条边在步行中至少被使用一次。 - 按照步行中边的使用顺序，将边的标签依次排列得到的字符串是一个合法的括号序列。 步行的定义如下：在图 $G$ 上，步行是一个由 $k$ 个顶点和 $k-1$ 条边交替组成的序列 $(v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k)$，其中每条边 $e_i$ 是从 $v_i$ 指向 $v_{i+1}$ 的有向边。$v_1$ 和 $v_k$ 分别称为步行的起点和终点。 合法的括号序列定义如下： - 空字符串是合法的括号序列。 - 如果 $A$ 是一个合法的括号序列，则 `(`、$A$、`)` 按顺序连接得到的字符串也是合法的括号序列。 - 如果 $A,B$ 是非空的合法括号序列，则 $A,B$ 按顺序连接得到的字符串也是合法的括号序列。

输入通过标准输入给出，格式如下： > $N$ $M$ $u_1$ $v_1$ $c_1$ $u_2$ $v_2$ $c_2$ $\vdots$ $u_M$ $v_M$ $c_M$

如果存在满足条件的步行，输出 `Yes`，否则输出 `No`。

### 限制条件 - $2 \leq N \leq 4000$ - $N \leq M \leq 8000$ - $1 \leq u_i, v_i \leq N$ - $c_i$ 是 `(` 或 `)` 之一 - $u_i \neq v_i$ - 如果 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$ - 输入的所有数值均为整数 - 输入给定的图中，对于任意两个顶点 $s,t$，都存在从 $s$ 到 $t$ 的路径 ### 样例解释 1 按顺序使用边 $1,2,3,4,1,5,6,7$ 的步行，所有边都至少被用过一次，且按使用顺序排列的标签字符串 `()()()()` 是一个合法的括号序列，因此满足条件。步行允许多次经过同一条边或同一顶点。 由 ChatGPT 4.1 翻译