← 返回题目列表

AtCoder · abc386_d

G. 对角线分离

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

分数: 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 B or W.
  • 所有输入数字均为整数。

输入

输入由标准输入按以下格式给出:

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