Edge Coloring

You are given a simple connected undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects the vertices $a\_i$ and $b\_i$.

Initially, the edges are not colored. Takahashikun wants to color the $i$-th edge with the color $c\_i$.

He can color the edges in the following way:

• First he chooses a vertex, and he repeats zero or more steps.
• In each step, he chooses a vertex adjacent to the current vertex and moves to the chosen vertex along an edge. This edge is colored red or blue (the color is defined according to the rule below).
• In odd-indexed (1-based) steps he uses red. In even-indexed steps he uses blue.
• If he colors an already-colored edges, the color of the edge is updated to the new color.

Determine if he can color all edges with correct colors.

$N$ $M$
$a\_1$ $b\_1$ $c\_1$
$a\_2$ $b\_2$ $c\_2$
$\vdots$
$a\_M$ $b\_M$ $c\_M$

Print "Yes", if Takahashikun can color all edges with correct colors or "No" otherwise.

• $2 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq a\_i < b\_i \leq N$
• The pairs $(a\_i, b\_i)$ are pairwise distinct.
• $c\_i$ is either an 'r' (red) or a 'b' (blue).
• The graph is connected.