← 返回题目列表

Codeforces · 1951/E

E. 没有回文

中文机器翻译题面 查看原题

给您一个由小写拉丁字符组成的字符串 $$$s$$$。您需要将$$$^\dagger$$$这个字符串分割成一些子字符串,使得每个子字符串都不是回文$$$^\ddagger$$$。

$$$^\dagger$$$ 字符串 $$$s$$$ 的分区是一些 $$$k$$$ 字符串 $$$t_1, t_2, \ldots, t_k$$$ 的有序序列,使得 $$$t_1 + t_2 + \ldots + t_k = s$$$,其中 $$$+$$$ 这里表示串联操作。

$$$^\ddagger$$$ 如果字符串 $$$s$$$ 向后读取的内容与向前读取的内容相同,则该字符串被视为回文。例如,$$$\mathtt{racecar}$$$、$$$\mathtt{abccba}$$$ 和 $$$\mathtt{a}$$$ 是回文,但 $$$\mathtt{ab}$$$、$$$\mathtt{dokibird}$$$ 和 $$$\mathtt{kurosanji}$$$ 不是回文。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例包含一个由小写拉丁字符组成的字符串 $$$s$$$ ($$$1 \le |s| \le 10^6$$$)。

保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,如果存在 $$$s$$$ 的分区,其部分不是回文,则打印一行“YES”,如果不存在这样的分区,则打印“NO”。

如果答案为“是”,则在第二行打印一个整数 $$$k$$$ — $$$s$$$ 需要划分的部分数量,以使每个部分都不是回文。在第三行,打印 $$$k$$$ 字符串 $$$t_1, t_2, \ldots, t_k$$$ 表示这样的分区。如果有多个这样的分区,则打印其中任何一个。

示例

输入 #1

3
sinktheyacht
lllllllll
uwuowouwu

输出 #1

YES
1
sinktheyacht
NO
YES
3
uw uow ouwu

注意

在第一个测试用例中,由于 $$$\mathtt{sinktheyacht}$$$ 已经是非回文,因此分区 $$$[\mathtt{sinktheyacht}]$$$ 有效。

在第二个测试用例中,由于字符串 $$$s$$$ 的任何子字符串都是回文,因此没有有效的分区。

在第三个测试用例中,另一个有效分区是 $$$[\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]$$$。