← 返回题目列表

Codeforces · 2092/D

D. 米什金劲量

中文机器翻译题面 查看原题

为了与老朋友费尔南决斗,埃德蒙正在准备一种名为“的能量饮料”米什金劲量“。该饮料由长度为 $$$n$$$ 的字符串 $$$s$$$ 组成,仅由字符组成 L, I,和 T,对应饮料中三种不同物质的含量。

我们称这种饮料为 平衡 如果它含有相同数量的所有物质。为了增强自己的气场并确保决斗的胜利,埃德蒙必须通过以下操作使初始字符串保持平衡:

  1. 选择一个索引 $$$i$$$,使得 $$$s_i \neq s_{i+1}$$$ (其中 $$$i + 1$$$ 不得超过 当前 字符串的大小)。
  2. 插入一个字符 $$$x$$$,或者 L, I,或 T,在它们之间使得 $$$x \neq s_i$$$ 和 $$$x \neq s_{i+1}$$$ 。

通过表演帮助埃德蒙使饮料平衡并赢得决斗 不超过 $$$\textbf{2n}$$$ 操作。如果有多个解,则可以输出其中任意一个。如果不可能,您必须报告此情况。

输入

每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由字符组成 L, I,和 T.

输出

对于每个测试用例,如果没有解决方案,则输出 $$$-1$$$。否则,在第一行中输出单个整数 $$$m$$$ ($$$0 \le m \le 2n$$$) — 您执行的操作数。

那么接下来的$$$m$$$行的第$$$l$$$行应该包含一个整数$$$i$$$ ($$$1 \le i \lt n+l-1$$$),表示在$$$s_i$$$和$$$s_{i+1}$$$之间插入一个字符的操作。它必须满足 $$$s_i \neq s_{i+1}$$$。

如果有多个解,则可以输出其中任意一个。请注意,您不需要最小化此问题中的操作数量。

示例

输入
复制

3
5
TILII
1
L
3
LIT

输出
复制

4
1
2
3
4
-1
0

注意

在第一个测试用例中,可以执行以下操作序列: 蒂利伊 $$$\右箭头$$$ TLILII $$$\右箭头$$$ TLTILII $$$\右箭头$$$ TLTLILII $$$\右箭头$$$ TLTLTILII.

在第二个测试用例中,无法执行任何操作,因此答案为$$$-1$$$。

在第三个测试用例中,初始字符串已具有等量的所有物质。