M1. Mondridalgo (Verification)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The motivating story and definition of a rectilinear path (and related terms) are the same in Mondridalgo (Verification) and (Optimization). Skip to the bolded text for the first section where the two differ.

Bob created a magnificent painting this year in the Mondridalgo style (a combination of Piet Mondrian's rectangles and Felix Hidalgo's neoclassicism), which both Alice and Cindy adore. Unfortunately, when Cindy asked him if she could keep the painting, he was too lovestruck and immediately said yes... forgetting that he had already previously promised the painting to Alice! Oh no! Remember everyone—don't be like Bob.

Unable to choose between his two friends, Bob decides the best way to resolve this situation is to cut up his painting into two contiguous pieces using a pair of scissors, and then hand one piece to Alice and the other Cindy. That way, each of his friends is equally unhappy.

We formalize "cutting with scissors" by defining a rectilinear path to be a non-empty sequence of "cuts" such that:

  • Each cut is represented by a directed line segment, indicating the motion of cutting.
  • The first cut starts somewhere along the border of the painting, and moves perpendicular to the border.
  • Each next cut in the sequence begins where the previous one ended, and is oriented perpendicular to the previous cut.
  • The final cut should end anywhere along the border.
A valid rectilinear path is one that partitions the painting into exactly two regions (one to hand to Alice and one to hand to Cindy). We can show that the following conditions make a rectilinear path valid:
  • All cuts are made along the gridlines, and with the exception of the start of the first cut and the end of the last cut, the path must stay entirely within the rectangle at all times.
  • Any two non-consecutive cuts should not intersect anywhere, not even at a point.
See the Notes below for illustrations of rectilinear cuts. Each one splits the painting into two regions, colored blue and red in the diagrams. They use $$$1$$$, $$$2$$$, and $$$4$$$ cuts, respectively.
For the verification problem, each square in the grid will be indicated as "should be given to Alice" or "should be given to Cindy". Does there exist a valid rectilinear path which partitions the painting into two regions in this manner? If yes, please also determine how many cuts are used in this rectilinear path. Also, please answer $$$T$$$ different test cases per file.
Input

The first line of input contains a single integer $$$T$$$. Then, the descriptions of each of the $$$T$$$ test cases follows.

The first line of each test case contains the two space separated integers $$$r$$$ and $$$c$$$.

Then, an $$$r \times c$$$ grid follows—that is, $$$r$$$ lines follow, each containing a string of length $$$c$$$, each one A or C. The letter A means that this square should go to Alice, and the letter C means that this square should go to Cindy.

Output

For each test case:

  • If the task is possible, output a line containing the word YES. Otherwise, output NO.
  • If YES, also output a line containing the number of cuts in the partition's rectilinear path.
Scoring

Let $$$A$$$ be the sum of $$$rc$$$ across all test files.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 100 \\ 2 \leq r, c \leq 400 \\ A \le 10^6 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{$r = c = 2$} \\ && \text{$T \le 16$} \\ \hline 2 & \mathbf{20} & \text{$r = 2$} \\ && \text{$c \leq 50$} \\ \hline 3 & \mathbf{20} & \text{$r \leq 3$} \\ && \text{$c \leq 50$} \\ \hline 4 & \mathbf{30} & \text{$r, c \leq 50$} \\ && \text{$A \le 20000$} \\ \hline 5 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
5
4 6
AAAAAA
AAAAAA
AAAAAA
CCCCCC
4 6
CCCCCC
CCCCCC
AACCCC
AACCCC
4 6
CCCCCC
ACCCCC
AAACCC
AAACCC
5 5
AACCA
AAACA
ACCCA
ACCAA
AAAAA
3 3
AAA
ACA
CAA
Output
YES
1
YES
2
YES
4
YES
9
NO
Note

The first three test cases correspond to the examples illustrated in the problem statement.