311219: CF1951E. No Palindromes

E. No Palindromestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputChristopher Tin ft. Soweto Gospel Choir - Baba Yetuඞ

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

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

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.

ExampleInput

3
sinktheyacht
lllllllll
uwuowouwu

Output

YES
1
sinktheyacht
NO
YES
3
uw uow ouwu

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}]$.

题目大意：
这个题目要求你将一个由小写拉丁字母组成的字符串 s 分割成若干子字符串，使得每个子字符串都不是回文。回文是指正读和反读都相同的字符串。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例包含一个字符串 s，由小写拉丁字母组成（1 ≤ |s| ≤ 10^6）。
- 保证所有测试用例的 s 长度之和不超过 10^6。

输出：
- 对于每个测试用例，如果存在一个分割使得 s 的每个部分都不是回文，则在一行内打印 "YES"，否则打印 "NO"。
- 如果答案为 "YES"，在第二行打印一个整数 k，表示将 s 分割成非回文部分所需的最少部分数。
- 在第三行打印 k 个字符串 t_1, t_2, ..., t_k，代表这样的一个分割。如果有多个这样的分割，打印其中任意一个。

示例：
输入：
```
3
sinktheyacht
lllllllll
uwuowouwu
```
输出：
```
YES
1
sinktheyacht
NO
YES
3
uw uow ouwu
```

注意：
- 在第一个测试用例中，由于 "sinktheyacht" 本身就不是回文，所以分割 ["sinktheyacht"] 是有效的。
- 在第二个测试用例中，由于字符串 s 的任何子串都是回文，所以没有有效的分割。
- 在第三个测试用例中，另一个有效的分割是 ["uw","uo", "wou", "wu"]。题目大意： 这个题目要求你将一个由小写拉丁字母组成的字符串 s 分割成若干子字符串，使得每个子字符串都不是回文。回文是指正读和反读都相同的字符串。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例包含一个字符串 s，由小写拉丁字母组成（1 ≤ |s| ≤ 10^6）。 - 保证所有测试用例的 s 长度之和不超过 10^6。 输出： - 对于每个测试用例，如果存在一个分割使得 s 的每个部分都不是回文，则在一行内打印 "YES"，否则打印 "NO"。 - 如果答案为 "YES"，在第二行打印一个整数 k，表示将 s 分割成非回文部分所需的最少部分数。 - 在第三行打印 k 个字符串 t_1, t_2, ..., t_k，代表这样的一个分割。如果有多个这样的分割，打印其中任意一个。 示例： 输入： ``` 3 sinktheyacht lllllllll uwuowouwu ``` 输出： ``` YES 1 sinktheyacht NO YES 3 uw uow ouwu ``` 注意： - 在第一个测试用例中，由于 "sinktheyacht" 本身就不是回文，所以分割 ["sinktheyacht"] 是有效的。 - 在第二个测试用例中，由于字符串 s 的任何子串都是回文，所以没有有效的分割。 - 在第三个测试用例中，另一个有效的分割是 ["uw","uo", "wou", "wu"]。