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.