AT_arc041_d.[ARC041D] 辺彩色

给定一个包含 $N$ 个顶点和 $M$ 条边的无向图。该图是连通的，不包含自环和重边。每条边从 $1$ 到 $M$ 编号。

初始时，所有边都没有被染色。高桥君希望第 $i$ 条边被染成颜色 $c_i$。其中，$c_i$ 为 r（红色）或 b（蓝色）。高桥君可以按如下方式对边进行染色：

• 首先，任选一个顶点作为起点。之后，可以任意多次重复“移动到相邻顶点”这一步骤。
• 每次移动时，经过的边会被染色。第奇数次移动时染成红色，第偶数次移动时染成蓝色。
• 如果经过的边已经被染色，则会被新颜色覆盖。

请判断是否存在一种移动方式，使得所有边都被染成目标颜色。

输入从标准输入中给出，格式如下：

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

• 第 $1$ 行包含两个整数 $N$（$2 \leq N \leq 2000$）和 $M$（$1 \leq M \leq 2000$），表示顶点数和边数。
• 接下来的 $M$ 行，每行包含两个整数 $a_i$、$b_i$（$1 \leq a_i < b_i \leq N$）和一个字符 $c_i$，表示第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，且目标颜色为 $c_i$（r 或 b）。
  • 对于任意 $i \neq j$，有 $a_i \neq a_j$ 或 $b_i \neq b_j$。
  • 图是连通的。

如果可以使所有边都被染成目标颜色，则输出 Yes，否则输出 No。输出后需换行。

样例解释 1

例如，可以选择顶点 $1$ 作为起点，按照图中的方式对边进行染色。

样例解释 2

例如，可以选择顶点 $2$ 作为起点，按照图中的方式对边进行染色。被覆盖的颜色用虚线表示。

由 ChatGPT 4.1 翻译