← 返回题目列表

Codeforces · 1784/B

B. 信件交换

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

合作游戏由 $$$m$$$ 人玩。游戏中有 $$$3m$$$ 张纸:带有字母“w”的 $$$m$$$ 张纸、带有字母“i”的 $$$m$$$ 张纸和带有字母“n”的 $$$m$$$ 张纸。

最初,每个人都会收到三张纸(可能带有相同的字母)。

游戏的目标是让每个 $$$m$$$ 人用他们的纸拼写出“win”这个词。换句话说,每个人都应该有一张带有字母“w”的纸,一张带有字母“i”的纸,一张带有字母“n”的纸。

为了实现目标,人们可以进行交流。每次交流都有两个人参与。两人从自己拥有的三张纸中恰好选出一张并互相交换。

找到最短的交换序列,之后每个人都有一个“w”、一个“i”和一个“n”。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$m$$$ ($$$2 \le m \le 10^5$$$) — 人数。

接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含长度为 $$$3$$$ 的字符串 $$$s_i$$$,由小写英文字母“w”、“i”和“n”组成,表示游戏开始时 $$$i$$$ 在纸上的字母,顺序任意。

每个字母“w”、“i”和“n”在纸张上总共出现了 $$$m$$$ 次。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个非负整数 $$$k$$$ — 让每个人都有一个“w”、一个“i”和一个“n”所需的最少交换次数。

在接下来的 $$$k$$$ 行中,打印四个标记 $$$a_1$$$ $$$c_1$$$ $$$a_2$$$ $$$c_2$$$,按时间顺序描述交换 ($$$1 \le a_1, a_2 \le m$$$; $$$a_1 \ne a_2$$$; $$$c_1, c_2$$$ 是 $$$\{\mathtt{w}, \mathtt{i}, \mathtt{n}\}$$$ 之一:人 $$$a_1$$$ 将字母 $$$c_1$$$ 给予人 $$$a_2$$$,而人 $$$a_2$$$ 同时将字母 $$$c_2$$$ 给予人 $$$a_1$$$。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

3
2
nwi
inw
3
inn
nww
wii
4
win
www
iii
nnn

输出 #1

0
2
2 w 3 i
3 w 1 n
3
2 w 3 i
2 w 4 n
3 i 4 n