CF1109B · Sasha and One More Name

• 难度：1800
• 标签：constructive algorithms、hashing、strings
• 链接：https://codeforces.com/problemset/problem/1109/B
• 时间限制：1 second　内存限制：256 megabytes
• 出现位置：Day21-字符串综合-hash-二分-构造

中文题意

给定一个回文串 $s$。你需要将它切割 $k$ 次，得到 $k+1$ 个子串（每一段都是原串的连续子串），然后把这些段重新排列拼接成一个新字符串。段不能翻转，只能改变顺序。

例如对字符串 f|de|abc|g 进行 $3$ 次切割后，交换 f 与 abc 两段可以得到 abcdefg；但用同样的切割无法得到 cbadefg。

求最小的 $k$，使得切成 $k+1$ 段并重新拼接后，能得到一个与原串 $s$ 不同的回文串。若无解，输出 Impossible（不含引号）。

输入格式（中文）

第一行一个字符串 $s$（$1 \le |s| \le 5\,000$），仅由小写拉丁字母组成。保证 $s$ 是回文串。

输出格式（中文）

输出一个整数 $k$，表示得到新名字所需的最少切割次数；若无解，输出 Impossible（不含引号，区分大小写）。

样例

样例 1

输入：

nolon

输出：

2

样例 2

输入：

otto

输出：

1

样例 3

输入：

qqqq

输出：

Impossible

样例 4

输入：

kinnikkinnik

输出：

1