Score: $700$ points

问题陈述

给定一个有向图 $G$，包含 $N$ 个顶点和 $M$ 条边。顶点编号从 $1$ 到 $N$，每条边都带有 ( 或 ) 的标签。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$，并带有标签 $c_i$。该图不包含多边或自环。

在这个图中，对于任意两个顶点 $s$ 和 $t$，都存在一条从 $s$ 到 $t$ 的路径。

确定是否存在一个图 $G$ 上的 遍历，满足以下所有条件：

• 遍历的起始和结束顶点是相同的。
• 对于 $i=1,2,\dots,M$，第 $i$ 条边在遍历中至少使用一次。
• 通过按使用顺序排列遍历中使用的边的标签得到的字符串是一个合法的括号序列。

什么是遍历？在图 $G$ 上的遍历是一个序列 $(v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k)$，包含 $k$ 个顶点（$k$ 是一个正整数）和 $k-1$ 条边，其中边 $e_i$ 从顶点 $v_i$ 指向顶点 $v_{i+1}$。顶点 $v_1$ 和 $v_k$ 分别称为遍历的起始和结束顶点。什么是合法的括号序列？

合法的括号序列是一个字符串，满足以下任一条件：

• 它是一个空字符串。
• 它是一个通过按顺序连接 (、一个合法的括号序列 $A$ 和 ) 得到的字符串。
• 它是一个通过按顺序连接两个非空的合法括号序列 $A$ 和 $B$ 得到的字符串。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and each edge is labeled with ( or ). The $i$-th edge is directed from vertex $u_i$ to vertex $v_i$ with a label $c_i$. The graph does not contain multi-edges or self-loops.

In this graph, for any two vertices $s$ and $t$, there is a path from $s$ to $t$.

Determine if there is a walk on the graph $G$ that satisfies all of the following conditions:

• The start and end vertices of the walk are the same.
• For $i=1,2,\dots,M$, the $i$-th edge is used at least once in the walk.
• The string obtained by arranging the labels of the edges used in the walk in the order of their usage is a regular bracket sequence.

What is a walk? A walk on a graph $G$ is a sequence $(v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k)$ of $k$ vertices ($k$ is a positive integer) and $k-1$ edges, where the edge $e_i$ is directed from vertex $v_i$ to vertex $v_{i+1}$. The vertices $v_1$ and $v_k$ are called the start and end vertices of the walk, respectively. What is a regular bracket sequence?

A regular bracket sequence is a string that satisfies one of the following conditions:

• It is an empty string.
• It is a string obtained by concatenating (, a regular bracket sequence $A$, and ) in this order.
• It is a string obtained by concatenating two non-empty regular bracket sequences $A$ and $B$ in this order.

Constraints

• $2 \leq N \leq 4000$
• $N \leq M \leq 8000$
• $1 \leq u_i,v_i \leq N$
• $c_i$ is ( or ).
• $u_i \neq v_i$
• If $i \neq j$, then $(u_i,v_i) \neq (u_j,v_j)$.
• All input values are integers.
• In the input graph, for any two vertices $s$ and $t$, there is a path from $s$ to $t$.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$u_1$ $v_1$ $c_1$

$u_2$ $v_2$ $c_2$

$\vdots$

$u_M$ $v_M$ $c_M$

Output

If there is a walk satisfying the conditions, print Yes; otherwise, print No.

Sample Input 1

5 7
1 2 (
2 3 )
3 4 (
4 1 )
2 4 )
4 5 (
5 1 )

Sample Output 1

Yes

The walk that uses edges $1,2,3,4,1,5,6,7$ in this order uses all the edges at least once, and the string ()()()() obtained by arranging the labels of the edges in the order of their usage is a regular bracket sequence, so all conditions are satisfied.

The walk may use the same edge multiple times or visit the same vertex multiple times.

Sample Input 2

2 2
1 2 )
2 1 )

Sample Output 2

No

Sample Input 3

10 20
4 5 (
5 6 (
6 7 )
2 5 )
5 8 (
6 3 )
8 5 )
1 2 (
9 10 (
4 7 (
3 4 )
8 9 (
2 1 )
1 4 )
2 3 )
3 2 (
7 8 (
7 4 )
10 9 )
9 8 )

Sample Output 3

Yes