题目描述

计算机协会会长失踪了！Yuki 和她的伙伴们为了找到会长，偷偷潜入了会长的寝室。Yuki 敏锐地意识到，在这个房间的内部，具备非侵蚀性融合的异次元空间在限制条件模式下单独发生了。（在略去了剧透内容后，）Yuki 发现会长失踪前正在访问 SOS 团官网，而官网上的 SOS 图标则在一系列缘由下包含了异界信息、引来了这一系列事件。

异界信息可以用一个字符串 $s$ 来表示。在每一秒内，Yuki 可以选择 $s$ 的一个子串 $s'$，然后如果 $s'$ 的首尾字符不同，那么从 $s$ 中删去 $s'$. Yuki 想知道她能不能清空整个 $s$（即能否以此法将 $s$ 删为空串）。如果能，她还想知道清空整个 $s$ 的最短用时。

输入格式

输入数据共一行一个字符串 $s\ (1 \leqslant |s| \leqslant 2\times10^6)$，保证 $s$ 中仅含英文大小写字母和下划线。

输出格式

输出共一行一个整数。如果能删除整个 $s$，输出最短用时秒数 $t$；否则输出 -1.

Mysterique_Sign

1

SOS

-1

样例解释

对于 $s=$ Mysterique_Sign，只需选择 $s'=s$，便可以在 $1$ 秒中将 $s$ 清空；

对于 $s=$ SOS，可以证明无论如何都无法将 $s$ 清空。