P14975 [USACO26JAN1] COW Splits B

Bessie is given a positive integer $N$ and a string $S$ of length $3N$ which is generated by concatenating $N$ strings of length $3$, each of which is a cyclic shift of $\texttt{COW}$. In other words, each string will be $\texttt{COW}$, $\texttt{OWC}$, or $\texttt{WCO}$. String $X$ is a square string if and only if there exists a string $Y$ such that $X = Y + Y$ where $+$ represents string concatenation. For example, $\texttt{COWCOW}$ and $\texttt{CC}$ are examples of square strings but $\texttt{COWO}$ and $\texttt{OC}$ are not. In a single operation, Bessie can remove any subsequence $T$ from $S$ where $T$ is a square string. A subsequence of a string is a string which can be obtained by removing several (possibly zero) characters from the original string. Your job is to help Bessie determine whether it is possible to transform $S$ into an empty string. Additionally, if it is possible, then you must provide a way to do so. Bessie is also given a parameter $k$ which is either $0$ or $1$. Let $M$ be the number of operations in your construction. - If $k = 0$, then $M$ must equal the minimum possible number of operations. - If $k = 1$, then $M$ can be up to one plus the minimum possible number of operations

The first line contains $T$, the number of independent test cases ($1\le T\le 10^4$) and $k$ ($0 \le k \le 1$). The first line of each test case has $N$ ($1 \le N \le 10^5$). The second line of each test case has $S$. The sum of $N$ across all test cases will not exceed $10^5$.

For each test case, output either one or two lines using the following procedure. If it is impossible to transform $S$ into an empty string, print $-1$ on a single line. Otherwise, on the first line print $M$ -- the number of operations in your construction. On the second line, print $3N$ space-separated integers. The $i$th integer $x$ indicates that the $i$th letter of $S$ was deleted as part of the $x$th subsequence ($1 \le x \le M$).

For the last test, the optimal number of operations is two, so any valid construction with either $M=2$ or $M=3$ would be accepted. For $M=3$, here is a possible construction: 1. In the first operation, remove the last twelve characters. Now we're left with $\texttt{COWCOW}$. 1. In the second operation, remove the subsequence `WW`. Now we're left with $\texttt{COCO}$. 1. In the last operation, remove all remaining characters. --- - Inputs 3-4: $T \le 10, N \le 6, k = 0$ - Inputs 5-6: $k = 1$ - Inputs 7-14: $k = 0$