链接: https://cses.fi/problemset/task/2427

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一排有 $2n$ 个盒子。有两个相邻的盒子是空的，其余所有盒子中有一个字母 "A" 或 "B"。两种字母都恰好出现在 $n-1$ 个盒子中。

你的任务是通过移动字母，使所有字母 "A" 都出现在任意字母 "B" 之前。每轮你可以选择任意两个相邻的、含有字母的盒子，并将这些字母移动到两个相邻的空盒子中，保持它们原有的顺序。

可以证明，要么存在一个由至多 $10n$ 轮组成的解决方案，要么根本不存在解决方案。

输入

第一行包含一个整数 $n$：共有 $2n$ 个盒子。

第二行包含一个长度为 $2n$ 的字符串，描述初始位置。每个字符是 "A"、"B" 或 "."（空盒子）。

输出

首先输出一个整数 $k$：轮数。之后输出 $k$ 行描述移动。你可以输出任意解，只要 $k \le 1000$。

如果无解，只输出 "-1"。

数据范围

$1 \le n \le 100$

样例输入1

3
AB..BA

样例输出1

2
ABBA..
A..ABB

样例输入2

3
ABAB..

样例输出2

-1