CF1109B Sasha and One More Name

阅读书籍是 Sasha 的一大爱好。有一次，他在读书时遇到了一个不同寻常的人物。这个人物这样介绍自己：“在许多国家我有许多名字。在精灵中我是 Mithrandir，矮人称我为 Tharkûn，年轻时在被遗忘的西方我是 Olórin，在南方是 Incánus，在北方是 Gandalf；我不去东方。” 此时 Sasha 想知道，这个人物在东方会被称为什么名字？在东方，所有的名字都是回文串。如果一个字符串正着读和反着读都一样，那么它就是回文串。例如，“kazak”、“oo” 和 “r” 都是回文串，而 “abb” 和 “ij” 不是。 Sasha 认为这个英雄会以东方某位神的名字命名。由于不能有两个相同的名字，所以东方的人们会这样做：他们把原始名字写成一个字符串在纸上，然后最少剪 $k$ 刀，把纸分成 $k+1$ 个子串，然后把这些子串重新组合成一个新字符串。子串不能翻转，但可以重新排列顺序。 这样，就可以通过 $3$ 刀将字符串 f|de|abc|g 重新排列成 abcdefg（比如交换 f 和 abc）。但无法用同样的切法得到 cbadefg。 更正式地说，给定一个回文串 $s$，Sasha 想要找到最小的 $k$，使得可以将该字符串切成 $k+1$ 段，然后重新组合这些段，得到一个新的回文串，并且这个新串不等于原始串 $s$。如果不存在这样的方案，输出 “Impossible”。

第一行包含一个字符串 $s$（$1 \le |s| \le 5000$）——原始名字，仅由小写拉丁字母组成。保证 $s$ 是回文串。

输出一个整数 $k$，表示获得新名字所需的最小切割次数。如果无解，输出 “Impossible”。

在第一个样例中，可以在如下位置切割字符串：no|l|on，然后重新组合为 on|l|no。可以证明，无法只切一次就得到答案。 在第二个样例中，可以正好在中间切一刀，然后交换两部分，得到 toot。 在第三个样例中，无法得到与原串不同的新回文串。 在第四个样例中，可以将后缀 nik 切下并放到开头，得到 nikkinnikkin。 由 ChatGPT 4.1 翻译