问题

给定由$N$个顶点和$M$条边组成的无向图。图是连通的，不包含自环和重复边。边被编号为$1$到$M$。

起初，边没有被涂上颜色。高桥君想要使第$i$（$1≤i≤M$）条边着上颜色$c_i$。其中$c_i$是r（红色）或b（蓝色）。高桥君按照以下方法对边进行着色：

• 首先，选择一个喜欢的顶点作为起点。然后，可以自由选择“移动到相邻顶点”这一步骤。
• 对每一步使用的边进行着色。在第奇数步时，用红色涂色；在第偶数步时，用蓝色涂色。
• 如果已经有颜色的边再次涂色，它将被新的颜色覆盖。

判断是否可以使所有的边都涂上目标颜色。

输入

输入以以下形式从标准输入中给出。

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

• 第$1$行包含两个整数，表示顶点数量$N$（$2≤N≤2,000$）和边数量$M$（$1≤M≤2,000$），以空格分隔。
• 从第$2$行开始的$M$行包含边的信息。其中第$i$行包含三个整数$a_i$，$b_i$（$1≤a_i<b_i≤N$）和颜色$c_i$，以空格分隔。表示如下：
  • 第$i$条边连接着顶点$a_i$和$b_i$。但是如果$i≠j$，这意味着$a_i≠a_j$或$b_i≠b_j$。
  • 希望为第$i$条边涂上颜色$c_i$。其中$c_i$是r（红色）或b（蓝色）。
• 图是连通的。

输出

如果可以使所有的边都涂上目标颜色，则输出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