解题思路

令 $dp[i]$ 表示把前缀 $s[0..i-1]$（长度为 $i$）切成同端片段的最多段数；若无法切分则为 $-1$。空前缀 $dp[0]=0$。

对每个字符 $c$，记录一个二元组 $(\textit{MAX}[c], \textit{index}[c])$：在以往某个位置 $index$ 处，字符恰好为 $c$，且当时前缀 $s[0..index-1]$ 的最优段数为 $\textit{MAX}$。

从左到右扫描，处理第 $i$ 个字符 $s[i-1]$ 时：

• 若该字符曾经作为某段的起点被记录过（$\textit{MAX}\ne -1$），则可以把 $s[index..i-1]$ 作为新的一段同端片段（首尾都是这个字符，且长度至少为 2），于是 $dp[i]=dp[index]+1$。

题目内容

给定一个仅含小写字母的字符串 $s$。一次切割会把它分成若干连续非空片段，且这些片段按原顺序拼回必须恰好等于 $s$。称一个片段为同端片段，当且仅当它的长度至少为 2，并且它的首字符与尾字符相同。

请把 $s$ 切成尽可能多的同端片段。若无论如何都无法把整个字符串切成同端片段（包括不切割但 $s$ 本身也不是同端片段的情况），则答案为 $-1$。

约束：字符串长度不超过 200000，且仅由小写字母组成。

输入描述

一行，一个仅包含小写字母的字符串 $s$。保证长度不超过 200000。

输出描述

输出一个整数：若存在合法切割，输出最多能得到的同端片段个数；否则输出 -1。

样例1

输入

aa

输出

1

说明

aa 长度恰好为 2 且首尾相同，是最短的同端片段。答案为 1。

样例2

输入

aaaa

输出

2

说明

可以切成 aa 与 aa 两段，每段都是同端片段。 这是能得到的最多段数，答案为 2。