AT_jsc2021_e.Level K Palindrome

高桥君为了表达对すぬけ君的感谢，决定送给他一个等级为 $K$ 的回文。等级为 $L$ 的回文（$L$ 是大于等于 $0$ 的整数）定义如下：

• 记字符串 $s$ 的左右反转为 $\mathrm{rev}(s)$。
• 当字符串 $s$ 满足 $s = \mathrm{rev}(s)$ 时，称 $s$ 为回文。
• 空字符串和非回文字符串被定义为等级 $0$ 的回文。
• 对于任意非空的等级 $L-1$ 的回文 $t$，将 $t$ 和 $\mathrm{rev}(t)$ 按顺序连接得到的字符串是等级 $L$ 的回文。
• 对于任意等级 $L-1$ 的回文 $t$ 和任意字符 $c$，将 $t$、$c$、$\mathrm{rev}(t)$ 按顺序连接得到的字符串是等级 $L$ 的回文。

现在，高桥君有一个字符串 $S$。
你可以多次（包括 $0$ 次）选择 $S$ 中的一个字符，将其改写为另一个小写英文字母。请判断是否可以通过若干次操作将 $S$ 变为恰好等级 $K$ 的回文。如果可以，请输出最少需要的改写次数；如果不可以，请输出 impossible。

输入以如下格式从标准输入读入。

$K$ $S$

如果可以构造出恰好等级 $K$ 的回文，输出所需的最小改写次数。
如果无法构造，输出 impossible。

限制条件

• $K$ 是整数
• $0 \leq K \leq 5 \times 10^5$
• $S$ 由小写英文字母组成
• $1 \leq |S| \leq 5 \times 10^5$

样例解释 1

aabaaaabaa 的等级计算如下：

• 空字符串是等级 $0$ 的回文。
• a 是（空字符串）、a、（空字符串）顺序连接而成，因此是等级 $1$ 的回文。
• aa 是 a、a 顺序连接而成，因此是等级 $2$ 的回文。
• aabaa 是 aa、b、aa 顺序连接而成，因此是等级 $3$ 的回文。
• aabaaaabaa 是 aabaa、aabaa 顺序连接而成，因此是等级 $4$ 的回文。
  因此，aabaaaabaa 本身就是等级 $4$ 的回文，不需要任何改写。

样例解释 2

例如，将 aabaaaabaa 改写为 acbcaacbca，可以得到恰好等级 $2$ 的回文。注意，aabaaaabaa 并不是等级 $2$ 的回文。

由 ChatGPT 4.1 翻译