「KDOI-10」反回文串

[English Statement](https://www.luogu.com.cn/problem/T519008). You must submit your code at the Chinese version of the statement. **本场比赛所有题目从标准输入读入数据，输出到标准输出。**

我们称一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i=r_{m+1-i}$ 对所有 $1\le i\le m$ 均成立。 给定一个长度为 $n$ 的字符串 $s$，你需要把 $s$ 分成若干个非空子序列，使得每一个子序列都**不是**回文的，并最大化划分成的子序列数。 形式化地说，你需要给出一组序列 $(a_1,a_2,\ldots,a_k)$，满足： - 对于任意 $1\le i\le k$，记 $l_i$ 为 $a_i$ 的长度，则 $l_i\ge 1$，且 $1\le a_{i,1}<a_{i,2}<\cdots<a_{i,l_i}\le n$； - 对于任意 $1\le i\le n$，恰好存在一个二元组 $(p,q)$，使得 $a_{p,q}=i$； - 对于任意 $1\le i\le k$，记字符串 $t=s_{a_{i,1}}s_{a_{i,2}}\ldots s_{a_{i,l_i}}$，则 $t$ 不是回文的。 在此基础上，你需要最大化 $k$ 的值；或者判断不存在一种合法的方案。 特别地，如果 $k$ 的值不是最大的，你也可能获得一定的部分分。

从标准输入读入数据。 **本题有多组测试数据。** 输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。 第二行包含一个正整数 $q$，表示测试数据组数。 对于每组测试数据： - 第一行包含一个正整数 $n$，表示字符串 $s$ 的长度； - 第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 中仅包含小写英文字母。

输出到标准输出。 对于每组测试数据： - 如果不存在一种合法的方案，输出一行一个字符串 `Shuiniao`； - 否则，你需要： - 在第一行输出一个字符串 `Huoyu`； - 第二行输出一个正整数 $k$ $(1\le k\le n)$，表示你划分成的子序列个数； - 接下来 $k$ 行，对于第 $i$ 行 $(1\le i\le k)$： - 首先输出一个正整数 $l_i$ $(1\le l_i\le n)$，表示第 $i$ 个子序列的长度； - 接下来输出 $l_i$ 个正整数 $a_{i,1},a_{i,2},\ldots, a_{i,l_i}$ $(1\le a_{i,j}\le n)$，表示第 $i$ 个子序列。 请注意，你的输出需要满足题目描述中所有的限制，否则，你将会得到 $0$ 分。

0
4
4
kdoi
7
ccccccc
7
sszcdjr
7
abacaca

Huoyu
2
2 1 2
2 3 4
Shuiniao
Huoyu
3
3 1 2 3
2 4 5
2 6 7
Huoyu
3
2 1 4
3 2 3 5
2 6 7

**【样例 1 解释】** 对于第一组测试数据，显然输出构成一个合法的子序列划分，并且 - 对于第一个子序列，$t=\tt{kd}$ 不是回文的； - 对于第二个子序列，$t=\tt{oi}$ 不是回文的。 故这是一组合法的输出。可以证明，对于这组测试数据，$2$ 是 $k$ 的最大可能值。 对于第二组数据，它的任意一个子序列都是回文的， 故显然不存在合法的划分方案。 **【样例 2】** 见选手目录下的 `anti/anti2.in` 与 `anti/anti2.ans`。 这个样例共有 $10$ 组数据，均满足 $n=1\,000$。其中第 $1\sim 3$ 组数据满足特殊性质 A，第 $4\sim 6$ 组数据满足特殊性质 B。 *** **【评分方式】** 本题共有 $20$ 个测试点，每个测试点满分 $5$ 分。 本题采用自定义校验器（special judge）评测。每组测试数据可能有多组解，你只需要给出**任意**一组。 在每个测试点中，你的得分是在所有测试数据上得分的最小值。对于每组测试数据： - 如果你错误地判断了是否有解或者给出了一组不合法的序列，你将会获得 $0$ 分； - 如果你正确判断了是否有解，并在有解时给出了一组合法的序列： - 如果 $k$ 的值不是最大的，你将会获得 $2$ 分； - 如果 $k$ 的值是最大的，你将会获得 $5$ 分。 *** **【数据范围】** 对于全部的测试数据，保证： - $1\le q\le 10$； - $1\le n\le 10^5$； - $s$ 中仅包含小写英文字母。 |测试点|$n\le$|特殊性质| |:--:|:--:|:--:| |$1,2$|$5$|无| |$3\sim 5$|$18$|无| |$6\sim 8$|$1\,000$|B| |$9\sim 11$|$1\,000$|无| |$12\sim 14$|$10^5$|A| |$15\sim 17$|$10^5$|B| |$18\sim 20$|$10^5$|无| - 特殊性质 A：保证 $n$ 是偶数，且 $s$ 中每个字符的出现次数都不超过 $\frac{n}{2}$； - 特殊性质 B：保证 $s$ 中仅有 `a` 和 `b`。 *** **【如何使用校验器】** 为了方便选手测试，在附件的 `anti` 目录下我们下发了 `checker.cpp` 文件作为样例校验器，选手可以编译该程序，并使用它校验自己的输出文件的结果是否**合法**。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。 编译命令为： ```sh g++ -o checker -std=c++14 -O2 checker.cpp ``` `checker` 的使用方式为： ```sh checker <input-file> <output-file> ``` 其中，参数 ` <input-file>` 与 `<output-file>` 依次表示输入文件与你的输出文件。 若你的输出中的数字大小范围不合法，则校验器会给出相应提示并立即退出。否则，校验器输出以下内容： - 在第 $i$ 行 $(1\le i\le q)$ 中，输出第 $i$ 组测试数据的详细提示信息； - 在第 $(q+1)$ 行，输出这个测试点的总结信息。 例如，对于样例 1 的输入与输出，校验器将会向屏幕打印如下内容： ```plain Test case 1: OK. Participant's answer is YES (Huoyu), and k=2. Test case 2: OK. Participant's answer is NO (Shuiniao). Test case 3: OK. Participant's answer is YES (Huoyu), and k=3. Test case 4: OK. Participant's answer is YES (Huoyu), and k=3. ok 4 / 4 test cases passed. (4 test cases) ``` 若将输出改为如下： ```plain Huoyu 2 2 1 2 2 3 4 Huoyu 1 7 1 2 3 4 5 6 7 Huoyu 3 3 1 2 3 2 4 5 2 6 7 Huoyu 3 2 1 4 3 2 3 5 2 6 7 ``` 则会向屏幕打印如下内容： ```plain Test case 1: OK. Participant's answer is YES (Huoyu), and k=2. Test case 2: Wrong answer. The string t obtained in the subsequence a[1] is palindrome. Test case 3: OK. Participant's answer is YES (Huoyu), and k=3. Test case 4: OK. Participant's answer is YES (Huoyu), and k=3. wrong answer 3 / 4 test cases passed. ``` **请注意：** 样例校验器只会检查你的输出是否合法，而**不会**： - 检查有解性是否判断正确； - 检查 $k$ 是否被最大化。 例如，将样例 1 的输出改为如下： ```plain Shuiniao Shuiniao Shuiniao Shuiniao ``` 此时，样例校验器仍会返回 `ok` 的检查结果。