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 翻译