#P1279. Sgu325 palindrome

    ID: 293 传统题 1000ms 512MiB 尝试: 91 已通过: 19 难度: 6 上传者: 标签>CF2000提高排序贪心同字符有序匹配求最少相邻交换次数树状数组奇偶性分析

Sgu325 palindrome

Description

回文串的定义就是一个字符串 CC 从前往后读和从后往前读一样。现在给你一个字符串 TT ,每次可以交换2个相邻的字符,你的目标就是通过尽可能少的次数使T变成回文串。如果无解,输出 Impossible

Input Format

第1行一个数 mm,表示有 mm 组数据。下面 mm 行,每行是一个字符串,长度不超过 10510^5。

Output Format

mm 行,每行一个数,表示最小交换次数。

2
abab
abc
1

Impossible

</p>

Hint

m≤10,n≤105m\leq 10,n\leq 10^5。