1951E · No Palindromes

Problem: You are given a string $s$ consisting of lowercase Latin characters. You need to partition$^\dagger$ this string into some substrings, such that each substring is not a palindrome$^\ddagger$.

$^\dagger$ A partition of a string $s$ is an ordered sequence of some $k$ strings $t_1, t_2, \ldots, t_k$, such that $t_1 + t_2 + \ldots + t_k = s$, where $+$ here represents the concatenation operation.

$^\ddagger$ A string $s$ is considered a palindrome if it reads the same backwards as forwards. For example, $\mathtt{racecar}$, $\mathtt{abccba}$, and $\mathtt{a}$ are palindromes, but $\mathtt{ab}$, $\mathtt{dokibird}$, and $\mathtt{kurosanji}$ are not.

Input Format: Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case contains a string $s$ consisting of lowercase Latin characters ($1 \le |s| \le 10^6$).

It is guaranteed that the sum of $|s|$ over all test cases does not exceed $10^6$.

Output Format: For each test case, print on one line "YES" if there exists a partition of $s$ whose parts are not palindromes, or "NO" if there is no such partition.

If the answer is "YES", on the second line, print an integer $k$ — the number of parts that $s$ needs to be partitioned to such that each part is not a palindrome. On the third line, print $k$ strings $t_1, t_2, \ldots, t_k$ representing such a partition. If there are multiple such partitions, print any of them.

Note: In the first test case, since $\mathtt{sinktheyacht}$ is already non-palindrome, the partition $[\mathtt{sinktheyacht}]$ is valid.

In the second test case, as any substring of the string $s$ is palindrome, there are no valid partitions.

In the third test case, another valid partition is $[\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]$.