Problem Description

You are given an undirected graph consisting of $ N $ vertices and $ M $ edges. The graph is connected and does not contain self-loops or multiple edges. Each edge is numbered from $ 1 $ to $ M $.

Initially, no edges are colored. Takahashi wants the $ i $ ($1 \leq i \leq M$) -th edge to be colored with $ c_i $, where $ c_i $ is either r (red) or b (blue). Takahashi colors the edges as follows:

• First, choose any vertex as the starting point. Then, repeat the step of "moving to an adjacent vertex" as many times as desired.
• Each step colors the used edge. On odd-numbered steps, paint the edge red, and on even-numbered steps, paint the edge blue.
• Coloring an already colored edge will overwrite the previous color with the new one.

Determine if it is possible to have all edges colored as desired.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ : $ a_M $ $ b_M $ $ c_M $

• The first line contains the number of vertices $ N $ ($2 \leq N \leq 2,000$) and the number of edges $ M $ ($1 \leq M \leq 2,000$) separated by a space.
• The next $ M $ lines contain the edge information. The $ i $-th line contains integers $ a_i $, $ b_i $ ($1 \leq a_i < b_i \leq N$) and color $ c_i $ separated by spaces, which means:
• The $ i $-th edge connects vertex $ a_i $ and vertex $ b_i $. Note that if $i \neq j$, then $a_i \neq a_j$ or $b_i \neq b_j$.
• The $ i $-th edge should be colored $ c_i $, where $ c_i $ is either r (red) or b (blue).
• The graph is connected.

Output Format

If it is possible to have all edges colored as desired, output Yes. Otherwise, output No. End the output with a newline.

Sample Input and Output

Sample Input #1

6 5
1 2 r
2 3 b
3 4 r
4 5 b
5 6 r

Sample Output #1

Yes

Sample Input #2

4 3
1 2 r
1 3 r
1 4 r

Sample Output #2

Yes

Sample Input #3

3 3
1 2 b
1 3 b
2 3 b

Sample Output #3

No

Notes/Hints

Sample Explanation 1

For example, choosing vertex $ 1 $ as the starting point and coloring the edges as shown in the figure can achieve the desired coloring.

Sample Explanation 2

For example, choosing vertex $ 2 $ as the starting point and coloring the edges as shown in the figure can achieve the desired coloring. Overwritten colors are indicated by dashed lines.

见题面 Input 部分

见题面 Output 部分