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 翻译