Maximal Non‐Palindromic Subsequence Partitioning

We call a string \( r \) of length \( m \) a palindrome if and only if \( r_i = r_{m+1-i} \) for all \( 1 \le i \le m \). Given a string \( s \) of length \( n \), your task is to partition the indices \( \{1,2,\dots,n\} \) into several nonempty subsequences such that the subsequence, when read in order, forms a string which is not a palindrome. Moreover, you must maximize the number of subsequences in your partition.

Formally, you need to produce a set of sequences \( (a_1, a_2, \ldots, a_k) \) satisfying the following conditions:

• For every \( 1 \le i \le k \), let \( l_i \) be the length of \( a_i \); then \( l_i \ge 1 \) and \( 1 \le a_{i,1} < a_{i,2} < \cdots < a_{i,l_i} \le n \).
• For every \( 1 \le j \le n \), there exists exactly one pair \( (p,q) \) such that \( a_{p,q} = j \) (i.e. the subsequences form a partition of \( \{1,2,\dots,n\} \)).
• For each \( 1 \le i \le k \), let \( t = s_{a_{i,1}} s_{a_{i,2}} \cdots s_{a_{i,l_i}} \) be the string corresponding to the \( i^\text{th} \) subsequence; then \( t \) is not a palindrome. Recall that a string of length \( 1 \) is always a palindrome.

If it is impossible to partition \( s \) in such a way, you should output -1. Otherwise, you are to output a valid partition whose number of subsequences \( k \) is maximized. Note that if \( s \) is partitionable, the maximum possible \( k \) is \( \frac{n}{2} \) if \( n \) is even and \( \frac{n-1}{2} \) if \( n \) is odd (since every subsequence must have length at least 2, except that when \( n \) is odd one of the subsequences must have length 3 or more).

Input format note: The input consists of a single line containing the string \( s \). The string \( s \) consists of English letters.

inputFormat

The input consists of a single line containing the string \( s \). For example:

aba

outputFormat

If there is no valid partition, output a single line containing -1. Otherwise, in the first line output the maximum number \( k \) of subsequences in the partition. Then output \( k \) lines. For each subsequence, first output its length \( l_i \), followed by \( l_i \) space‐separated integers representing the 1-indexed positions in \( s \) that comprise this subsequence.

For example, a valid output for the input abb is:

1
3 1 2 3

sample

aba

-1