← 返回题目列表

Codeforces · 1109/B

B. 萨莎和另一个名字

中文机器翻译题面 查看原题

读书是 Sasha 的爱好之一。有一次,他在读一本书时,认识了一个不寻常的人物。这个角色这样讲述自己:“在许多国家,我的名字有很多。精灵中的米斯兰迪尔,矮人中的塔昆,奥洛林。我年轻时在被遗忘的西方,在南印卡努斯,在北甘道夫;我没有去东方。”

在那一刻,萨沙想,这个角色在东方该怎么称呼?在东方,所有名字都是回文。如果一个字符串向后读与向前读相同,则该字符串是回文。例如,“kazak”、“oo”和“r”等字符串是回文,但字符串“abb”和“ij”则不是回文。

萨沙相信英雄将以东方诸神之一的名字命名。只要不能有两个相同的名字,那么在东方,人们就会这样做:他们把原来的名字作为字符串写在一张纸上,然后将纸剪裁最少$$$k$$$次,这样就得到了$$$k+1$$$张纸,其中包含初始字符串的子字符串,然后将这些碎片组合在一起得到新的字符串。棋子不能翻转,只能洗牌。

通过这种方式,可以使用 $$$3$$$ 剪切从字符串 f|de|abc|g 中获得字符串 abcdefg(通过用子字符串 f 和 abc 交换文件)。使用相同的剪切无法接收字符串 cbadefg。

更正式地说,Sasha 希望对于给定的回文 $$$s$$$ 找到这样的最小值 $$$k$$$,您可以将此字符串切割成 $$$k + 1$$$ 部分,然后以最终字符串将是回文的方式将它们联合起来,并且它不会等于初始字符串 $$$s$$$。如果没有答案,则打印“Impossible”(不带引号)。

输入

第一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 5\,000$$$) - 初始名称,仅由小写拉丁字母组成。保证 $$$s$$$ 是回文。

输出

打印一个整数 $$$k$$$ — 获得新名称所需的最少切割次数,或“不可能”(不带引号)。

示例

输入 #1

nolon

输出 #1

2

输入 #2

otto

输出 #2

1

输入 #3

qqqq

输出 #3

Impossible

输入#4

kinnikkinnik

输出#4

1

注意

在第一个示例中,您可以在以下位置剪切字符串:no|l|on,然后按如下方式将它们联合起来 on|l|no。可以证明,不存在一刀切的解。

在第二个示例中,您可以在中间切断字符串,并交换和平,这样您就会发出嘟嘟声。

在第三个示例中,您无法创建一个字符串,它不会等于第一个字符串。

在第四个示例中,您可以删除后缀 nik 并将其添加到开头,这样您就得到 nikkinnikkin。