给定一个包含 $N$ 个顶点和 $M$ 条边的简单连通无向图。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

初始时，所有边均未着色。Takahashikun 想要将第 $i$ 条边染成颜色 $c_i$。他可以通过以下方式为边着色：

• 首先，他选择一个顶点，并重复零次或多次移动。
• 在每一步中，他选择当前顶点的一个邻接顶点，并沿着边移动到该顶点。这条边会被染成红色或蓝色（颜色根据下述规则定义）。
• 在奇数次（从 1 开始计数）移动中，他使用红色。在偶数次移动中，他使用蓝色。
• 如果他为一条已经着色的边着色，该边的颜色将更新为新颜色。

请判断他是否能将所有边染成正确的颜色。

输入格式

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

数据范围

• $2 \le N \le 2000$
• $1 \le M \le 2000$
• $1 \le a_i < b_i \le N$
• 所有点对 $(a_i, b_i)$ 互不相同。
• $c_i$ 为 'r'（红色）或 'b'（蓝色）。
• 图是连通的。

输出格式

如果 Takahashikun 可以将所有边染成正确的颜色，输出 “Yes”，否则输出 “No”。

样例

输入格式 1

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

输出格式 1

Yes

说明

从顶点 1 开始。

输入格式 2

4 3
1 2 r
1 3 r
1 4 r

输出格式 2

Yes

说明

从顶点 2 开始。虚线表示被覆盖的颜色。

输入格式 3

3 3
1 2 b
1 3 b
2 3 b

输出格式 3

No