题目背景

English Statement. 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$		无
$12\sim 14$	$10^5$	A
$15\sim 17$		B
$18\sim 20$		无

• 特殊性质 A：保证 $n$ 是偶数，且 $s$ 中每个字符的出现次数都不超过 $\frac{n}{2}$；
• 特殊性质 B：保证 $s$ 中仅有 a 和 b。

---

【如何使用校验器】

为了方便选手测试，在附件的 anti 目录下我们下发了 checker.cpp 文件作为样例校验器，选手可以编译该程序，并使用它校验自己的输出文件的结果是否合法。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：

g++ −o checker -std=c++14 -O2 checker.cpp

checker 的使用方式为：

checker <input-file> <output-file>

其中，参数 <input-file> 与 <output-file> 依次表示输入文件与你的输出文件。

若你的输出中的数字大小范围不合法，则校验器会给出相应提示并立即退出。否则，校验器输出以下内容：

• 在第 $i$ 行 $(1\le i\le q)$ 中，输出第 $i$ 组测试数据的详细提示信息；
• 在第 $(q+1)$ 行，输出这个测试点的总结信息。

例如，对于样例 1 的输入与输出，校验器将会向屏幕打印如下内容：

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)

若将输出改为如下：

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

则会向屏幕打印如下内容：

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 的输出改为如下：

Shuiniao
Shuiniao
Shuiniao
Shuiniao

此时，样例校验器仍会返回 ok 的检查结果。