D - Diagonal Separation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 425

問題文

NN 列のグリッドがあります。高橋君は以下の条件を満たすように各マスを黒または白のいずれかに塗り分けたいと考えています。

  • すべての行について以下の条件が成り立つ。
    • ある整数 i\ (0\leq i\leq N) が存在して、その行の左から i 個のマスは黒、それ以外は白で塗られている。
  • すべての列について以下の条件が成り立つ。
    • ある整数 i\ (0\leq i\leq N) が存在して、その列の上から i 個のマスは黒、それ以外は白で塗られている。

M 個のマスがすでに塗られています。そのうち i 個目は上から X_i 行目、左から Y_i 列目のマスで、C_iB のとき黒で、 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_iB または 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

塗られていない残りの 2 つのマスをどのように塗っても,条件を満たすことはできません。


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

Score : 425 points

Problem Statement

There is an N \times N grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:

  • For every row, the following condition holds:
    • There exists an integer i\ (0\leq i\leq N) such that the leftmost i cells are colored black, and the rest are colored white.
  • For every column, the following condition holds:
    • There exists an integer i\ (0\leq i\leq N) such that the topmost i cells are colored black, and the rest are colored white.

Out of these N^2 cells, M of them have already been colored. Among them, the i-th one is at the X_i-th row from the top and the Y_i-th column from the left, and it is colored black if C_i is B and white if C_i is W.

Determine whether he can color the remaining uncolored N^2 - M cells so that all the conditions are satisfied.

Constraints

  • 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.
  • All input numbers are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

Output

If it is possible to satisfy the conditions, print Yes; otherwise, print No.


Sample Input 1

4 3
4 1 B
3 2 W
1 3 B

Sample Output 1

Yes

For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.


Sample Input 2

2 2
1 2 W
2 2 B

Sample Output 2

No

No matter how the remaining two cells are colored, the conditions cannot be satisfied.


Sample Input 3

1 1
1 1 W

Sample Output 3

Yes

Sample Input 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

Sample Output 4

No