问题描述

有一个 $N \times N$ 的网格。Takahashi 想要用黑色或白色为网格中的每个单元格上色，使得以下所有条件都得到满足：

• 对于每行，存在一个整数 $i(0 \leq i \leq N)$，使得左 $i$ 个单元格为黑色，剩下的单元格为白色。
• 对于每列，存在一个整数 $i(0 \leq i \leq N)$，使得上 $i$ 个单元格为黑色，剩下的单元格为白色。

在这 $N^2$ 个单元格中，已有 $M$ 个单元格被预先上色。其中，第 $i$ 个单元格位于第 $X_i$ 行的顶部和第 $Y_i$ 列的左侧，如果 $C_i$ 是 B，那么该单元格为黑色，如果 $C_i$ 是 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$ 为 B 或 W。
• 所有输入数字均为整数。

示例输入 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

此问题来自 atcoder比赛问题：abc386_d-Diagonal Separation