#1833. AT_abc386_d-Diagonal Separation

AT_abc386_d-Diagonal Separation

Problem Statement

There is an N×NN \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 (0iN)i\ (0\leq i\leq N) such that the leftmost ii cells are colored black, and the rest are colored white.

For every column, the following condition holds:

There exists an integer i (0iN)i\ (0\leq i\leq N) such that the topmost ii cells are colored black, and the rest are colored white.

Out of these N2N^2 cells, MM of them have already been colored. Among them, the ii-th one is at the XiX_i-th row from the top and the YiY_i-th column from the left, and it is colored black if CiC_i is B and white if CiC_i is W. Determine whether he can color the remaining uncolored N2MN^2 - M cells so that all the conditions are satisfied.

Constraints

1N1091\leq N\leq 10^9 1Mmin(N2,2×105)1\leq M\leq \min(N^2,2\times 10^5) 1Xi,YiN1\leq X_i,Y_i\leq N (Xi,Yi)(Xj,Yj) (ij)(X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j) CiC_i is B or W. All input numbers are integers.

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

abc386_d-Diagonal Separation