牛牛的字符串

题号：NC207507
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

牛牛正在给大家讲字符串定义！这是一位学生的笔记：

对于一个字符串 $S$ ，定义 $S_i$ 表示字符串 $S$ 的第 $i$ 个字符，其中 $i \in [1,|S|]$
定义一个字符串 $S$ 是回文串当且仅当满足 $\forall{i \in [1,|S|]},S_i = S_{|S|-i+1}$
定义字符串的拼接操作符为 $+$ ， $S+T$ 表示将字符串 $T$ 接到 $S$ 后面，例如 $aa+bb = aabb$
定义一个字符串 $S$ 的大小为 $k$ 的划分是字符串序列 $S_1,S_2,\ldots,S_k$ ，满足 $S = S_1+S_2+\ldots+S_k$

现在牛牛留下了一份课后作业：给你一个仅有小写字母组成的字符串 $S$ ，你能否找出一个最大的划分 $S_1,S_2,\ldots,S_k$ ，满足 $\forall i \in [1,k],S_i$ 都不是回文串吗？但是牛牛觉得这个题目太简单了就随手加强了一下：要求给出任意一种可行的方案。

显然出题人不可能会这个题于是把这个问题丢给了你。

划分最大是指划分的段数最大。

一行一个字符串，表示

第一行一个整数   表示最大的划分。

接下来  行，每行一个字符串 表示划分的方案。

特别的，如果不能找到任意一组合法的划分 只需要输出

示例1

复制

abbaca

复制

3
ab
ba
ca

示例2

复制

abbab

复制

2
abb
ab

示例3

复制

ababa

复制

-1