Description

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}<\dots<a_{i,l_i}\leq n$;
• For each $1\le i\le n$, there is exactly one integer pair $(p,q)$ such that $a_{p,q}=i$;
• For each $1\le i\le k$, let string $t:=s_{a_{i,1}}s_{a_{i,2}}\dots s_{a_{i,l_i}}$, then $t$ is not palindrome.

You have to maximize $k$, or determine there is no solution.

Specially, if your $k$ is not maximized, you may still get partial scores.

Input Format

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.

Output Format

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.

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

Hint

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.

• 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:

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

You can use checker.cpp like this:

checker <input-file> <output-file>

Parameters <input-file> and <output-file> 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:

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:

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:

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:

Shuiniao
Shuiniao
Shuiniao
Shuiniao

checker.cpp will still report ok as a result.