T519008 「KDOI-10」Anti-palindrome

[Chinese Statement](https://www.luogu.com.cn/problem/T502293?contestId=200849). You must submit your code at the Chinese version of the statement. |Input|Output|Time Limit|Memory Limit| |:--:|:--:|:--:|:--:| |standard input|standard output|1.0 s|512 MiB| This problem has $20$ tests. The full score is $100$ points, and $5$ points per test.

We call a string $r$ with length $m$ *palindrome* if and only if for each $1\le i\le m$, $r_i=r_{m+1-i}$ holds. Given a string $s$ of length $n$, you have to divide $s$ into several non-empty subsequences such that each of these subsequences is **not** palindrome, and maximize the number of subsequences. Formally, you have to find a group of sequences $(a_1,a_2,\dots a_k)$ such that: - For each $1\le i\le k$, let $l_i$ be the length of $a_i$, then $l_i\ge 1$ and $1\leq a_{i,1}< a_{i,2}

**Each test contains multiple test cases.** The first line of the input contains a single integer $c$ — the id of the test. $c=0$ represents that this is a sample test. The second line contains a single integer $q$ — the number of test cases. For each test case: - The first line contains a single integer $n$ — the length of the string $s$. - The second line contains a string $s$ length $n$. It is guaranteed that $s$ only contains lowercase English letters.

For each test case: - If there is no valid solution, print single string `Shuiniao` on the only line of output. - Otherwise, you have to: - Print a sinle string `Huoyu` on the first line; - Print an integer $k$ $(1\le k\le n)$ — the number of subsequences such that the string $s$ is divided into; - For the $i$-th line of the next $k$ lines $(1\le i\le k)$: - First, output an integer $l_i$ $(1\le l_i\le n)$ — the length of the $i$-th subsequence; - Next, output $l_i$ integers $a_{i,1},a_{i,2},\ldots, a_{i,l_i}$ $(1\le a_{i,j}\le n)$ — the $i$-th subsequence. Note that your output should satisfy all the constraints above, otherwise, you will get $0$ points in corresponding tests.

**Sample 1 Explanation** In the first test case, it is obvious that the output satisfies the constraints. And: - For the first subsequence, $t=\tt{kd}$ which is not palindrome. - For the second subsequence, $t=\tt{oi}$ which is not palindrome. As a result, this is a valid output. It can be proven that for this test case, the maximum possible value of $k$ is $2$. In the second test case, all of subsequences of $s$ are palindrome, so it is obvious that there is no solution. **Sample 2** See `anti/anti2.in` and `anti/anti2.ans` in the attachments. This sample has $10$ test cases, all satisfying $n=1\,000$. Among them, the first to third test cases satisfy property A and the fourth to sixth test cases satisfy property B. *** **Scoring** This problem has $20$ tests and each worth $5$ points. This problem is judged using ___Special Judge___. Each test case might have multiple solutions and you only need to output one of them. In each test, your score is the minimum number of points you receive in each test case. For each test case: - If you incorrectly judged whether there is a solution or print an invalid solution, no points will be given. - If you correctly judged whether there is a valid solution and print a valid solution: - If $k$ is not maximized, $2$ points will be given. - If $k$ is maximized, $5$ points will be given. *** **Constraints** For all the tests, it is guaranteed that: - $1\le q\le 10$; - $1\le n\le 10^5$; - $s$ only contains lowercase English letters. |Test Id|$n\le$|Special Properties| |:--:|:--:|:--:| |$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$|-| - Property A: It is guaranteed that $n$ is even and each type of letter in $s$ appears no more than $\frac{n}{2}$ times. - Property B: It is guaranteed that $s$ only consists of `a` or `b`. *** **How to Use the Checker** To help participants test their program, in the `anti` directory in the attachments, `checker.cpp` is provided. Participants can compile their codes and check whether the output is **valid** with it. Note that it is not exactly the same as the checker in final testing. You needn't care its content. The compile commands are: ```sh g++ −o checker -std=c++14 -O2 checker.cpp ``` You can use `checker.cpp` like this: ```sh checker ``` Parameters ` ` and `` are respectively the input file and your output file. If your output is out of range, the checker will report it and exit immediately. Otherwise, the checker will do the following things: - In the $i$-th line $(1\le i\le q)$, output the detail of the $i$-th test case. - In the $(q+1)$-th line, output the summary of this test. As an example, for the input and output of the first sample, the checker will output the following things to the screen: ```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) ``` If the output file is changed to this: ```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 ``` Then the checker will output the following things to the screen: ```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. ``` **Note that** `checker.cpp` will only check whether your output is valid, and **will not**: * Check whether you correctly judge if there's a valid solution. * Check whether $k$ is maximized. As an example, if the output file of sample $1$ is changed to this: ```plain Shuiniao Shuiniao Shuiniao Shuiniao ``` `checker.cpp` will still report `ok` as a result.