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 翻译