CF1784B Letter Exchange

有 $m$ 个人参与一个合作游戏。在游戏中，有 $3m$ 张纸条：$m$ 张写有字母 'w'，$m$ 张写有字母 'i'，$m$ 张写有字母 'n'。 最开始，每个人会分到三张纸条（可能有重复的字母）。 游戏的目标是让每个人都能用手中的纸条拼出单词 "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 \in \{\mathtt{w}, \mathtt{i}, \mathtt{n}\}$）：第 $a_1$ 个人将字母 $c_1$ 给第 $a_2$ 个人，同时第 $a_2$ 个人将字母 $c_2$ 给第 $a_1$ 个人。 如果有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译