← 返回题目列表

AtCoder · arc041_d

D. 边缘着色

中文机器翻译题面 查看原题

問題文

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 行输出。 在输出末尾插入换行符。


入力例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