Matrix Diagonal Blackening

Little Q, a very clever kid, loves playing a computer puzzle game called the Matrix Game. The game is played on an n × n board with black and white squares (similar to a chessboard but with arbitrary color distribution). The board can be manipulated by performing the following two operations any number of times:

• Row Swap: Choose any two rows in the matrix and swap them (i.e. swap the colors of the corresponding cells).
• Column Swap: Choose any two columns in the matrix and swap them (i.e. swap the colors of the corresponding cells).

The objective of the game is to use these operations to rearrange the board so that every cell on the main diagonal (from the top-left to the bottom-right) is black. For some levels, Little Q was puzzled and began to wonder whether a solution even exists for a given board. Help him by writing a program to determine whether it is possible to rearrange the board such that every cell on the main diagonal is black.

Note: Since row and column swaps can be performed arbitrarily, the problem reduces to the following: Given an n × n board, determine if there exists a permutation of rows and a permutation of columns such that for every i (0-indexed), the cell at position (i, i) (after the rearrangements) is originally black. Equivalently, check if there exists a perfect matching in the bipartite graph where rows are matched to columns if the corresponding cell is black.

All formulas are given in LaTeX format. For example, the board size is represented as $n \times n$, and the main diagonal refers to cells $(i, i)$ for $0 \leq i < n$.

inputFormat

The input consists of:

1. An integer n ($1 \leq n \leq 1000$) on the first line, representing the number of rows and columns.
2. n subsequent lines each containing a string of length n. Each character is either 'B' representing a black cell or 'W' representing a white cell.

For example:

3
BWB
WBB
BBW

outputFormat

Output a single line containing YES if it is possible to rearrange the board so that all the cells on the main diagonal are black, and NO otherwise.

sample

3
BWB
WBB
BBW

YES