問題文
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