#P18046. Beautiful Dangos
Beautiful Dangos
Beautiful Dangos
给定长度为 的字符串 ,每个字符都是 C、W、P 之一。若任意两个相邻字符都不同,则称这个字符串是美丽的。
你可以选择一个非空连续区间 ,将这个区间内的字符任意重新排列,区间外的字符保持不变。请让整个字符串变得美丽,并使所选区间的长度 最小。你需要输出最短区间和重排后的完整字符串。
若原字符串已经美丽,或者不存在任何可行重排,则按下方要求报告。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含两行:第一行一个整数 ,第二行是字符串 。
输出格式
对每个测试用例:
- 若原字符串已经美丽,仅输出一行
Beautiful。 - 否则,若无论怎样重排都不可能变美丽,仅输出一行
Impossible。 - 否则输出三行:第一行
Possible;第二行两个整数 ;第三行重排后的长度为 的完整字符串。
区间必须是最短可行区间。如果最优方案不唯一,输出任意一种。只要求方案合法并达到最短长度,不要求与标准输出的区间或字符串完全相同。
数据范围
,。一个输入文件中所有测试用例的 之和不超过 。
样例 1
输入:
4
5
CWCWC
6
CWCCPW
3
PPP
8
CWPPCWWC
输出:
Beautiful
Possible
4 5
CWCPCW
Impossible
Possible
4 6
CWPWCPWC