分数: 425 点
问题陈述
有一个 N \times N 网格。高桥希望将每个单元格着色为黑色或白色,以便满足以下所有条件:
- 对于每一行,以下条件成立:
- 存在一个整数 i\ (0\leq i\leq N) 这样最左边的 i 单元格为黑色,其余为白色。
- 对于每一列,以下条件成立:
- 存在一个整数 i\ (0\leq i\leq N) 这样最上面的 i 单元格为黑色,其余为白色。
其中 N^2 细胞,
其中 M 已经上色了。其中, i- 第一个位于 X_i从顶部开始的第行和 Y_i从左边算起第 1 列,如果 C_i is B 和白色如果 C_i is W.
判断他是否可以给剩下的未着色的着色 N^2 - M 单元格,以便满足所有条件。
约束
- 1\leq N\leq 10^9
- 1\leq M\leq \min(N^2,2\times 10^5)
- 1\leq X_i,Y_i\leq N
- (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
- C_i is
BorW. - 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
N M X_1 Y_1 C_1 \vdots X_M Y_M C_M
输出
如果可以满足条件,则打印 Yes;否则,打印 No.
样本输入 1
4 3 4 1 B 3 2 W 1 3 B
示例输出 1
Yes
例如,可以如下图所示为网格着色以满足条件。已经着色的单元格被红色边框包围。

示例输入 2
2 2 1 2 W 2 2 B
示例输出 2
No
无论剩下的两个单元格如何着色,都无法满足条件。
示例输入 3
1 1 1 1 W
示例输出 3
Yes
示例输入 4
2289 10 1700 1083 W 528 967 B 1789 211 W 518 1708 W 1036 779 B 136 657 B 759 1497 B 902 1309 B 1814 712 B 936 763 B
示例输出 4
No