English · Original
Chinese · Translation
Formal · Original
*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:
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.
For each test case:
Let $A$ be the sum of $r c$ 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*}$$
The first three test cases correspond to the examples illustrated in the problem statement.
## 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.
[samples]
## Scoring
Let $A$ be the sum of $r c$ 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*}$$
## Note
The first three test cases correspond to the examples illustrated in the problem statement.
[{"iden":"statement","content":"*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.*\n\nBob 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.\n\nUnable 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.\n\nWe formalize \"cutting with scissors\" by defining a _rectilinear path_ to be a non-empty sequence of \"cuts\" such that: \n\nThe first line of input contains a single integer $T$. Then, the descriptions of each of the $T$ test cases follows.\n\nThe first line of each test case contains the two space separated integers $r$ and $c$.\n\nThen, 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.\n\nFor each test case:\n\nLet $A$ be the sum of $r c$ across all test files.\n\n$$\\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*}$$\n\nThe first three test cases correspond to the examples illustrated in the problem statement.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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. "},{"iden":"scoring","content":"Let $A$ be the sum of $r c$ 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*}$$"},{"iden":"note","content":"The first three test cases correspond to the examples illustrated in the problem statement."}]}
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ r_k, c_k \in \mathbb{Z} $ denote the dimensions of the grid.
- Let $ G_k \in \{A, C\}^{r_k \times c_k} $ be a grid where each cell is labeled $ A $ or $ C $.
**Constraints**
1. $ 1 \leq T \leq 100 $
2. $ 2 \leq r_k, c_k \leq 400 $ for all $ k $
3. Let $ A = \sum_{k=1}^T r_k c_k $; then $ A \leq 10^6 $
**Objective**
Find a rectilinear path (a connected sequence of horizontal/vertical cuts along grid edges) that divides $ G_k $ into two non-empty contiguous regions, such that the number of $ A $'s in one region equals the number of $ C $'s in the other (or equivalently, the difference in counts of $ A $ and $ C $ between the two regions is zero).
*(Note: The exact formal definition of "rectilinear path" as a cutting boundary is implied by grid-edge traversal; the objective is to partition the grid into two connected components with balanced $ A $ and $ C $ assignments.)*
API Response (JSON)
{
"problem": {
"name": "M1. Mondridalgo (Verification)",
"description": {
"content": "*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 tw",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFM1"
},
"statements": [
{
"statement_type": "Markdown",
"content": "*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 tw...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"*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 fo...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T \\in \\mathbb{Z} $ be the number of test cases. \nFor each test case $ k \\in \\{1, \\dots, T\\} $: \n- Let $ r_k, c_k \\in \\mathbb{Z} $ denote the dimensions of the grid. \n- Let $...",
"is_translate": false,
"language": "Formal"
}
]
}