CF1784B.Letter Exchange

A cooperative game is played by $m$ people. In the game, there are $3m$ sheets of paper: $m$ sheets with letter 'w', $m$ sheets with letter 'i', and $m$ sheets with letter 'n'.

Initially, each person is given three sheets (possibly with equal letters).

The goal of the game is to allow each of the $m$ people to spell the word "win" using their sheets of paper. In other words, everyone should have one sheet with letter 'w', one sheet with letter 'i', and one sheet with letter 'n'.

To achieve the goal, people can make exchanges. Two people participate in each exchange. Both of them choose exactly one sheet of paper from the three sheets they own and exchange it with each other.

Find the shortest sequence of exchanges after which everyone has one 'w', one 'i', and one 'n'.

一个合作游戏由 $m$ 个人参与。游戏中共有 $3m$ 张纸片：其中 $m$ 张印有字母 'w'，$m$ 张印有字母 'i'，$m$ 张印有字母 'n'。

初始时，每人分得三张纸片（这些纸片上的字母可能相同）。

游戏的目标是让这 $m$ 个人均能用自己手中的纸片拼出单词 "win"。换言之，每个人都必须恰好拥有一张 'w'、一张 'i' 和一张 'n'。

为达成目标，参与者可进行交换操作。每次交换由两人参与：双方各自从自己当前持有的三张纸片中恰好选择一张，并相互交换。

请找出使所有人最终都恰好拥有一张 'w'、一张 'i' 和一张 'n' 所需的最少交换次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $m$ ($2 \le m \le 10^5$) — the number of people.

The $i$-th of the next $m$ lines contains a string $s_i$ of length $3$ consisting of lowercase English letters 'w', 'i', and 'n', denoting the letters person $i$ has on their sheets of paper at the beginning of the game, in arbitrary order.

Each of the letters 'w', 'i', and 'n' appears on the sheets of paper exactly $m$ times in total.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a non-negative integer $k$ — the smallest number of exchanges people need to make everyone have one 'w', one 'i', and one 'n'.

In each of the next $k$ lines print four tokens $a_1$ $c_1$ $a_2$ $c_2$, describing the exchanges in chronological order ($1 \le a_1, a_2 \le m$; $a_1 \ne a_2$; $c_1, c_2$ are one of ${\mathtt{w}, \mathtt{i}, \mathtt{n}}$): person $a_1$ gives letter $c_1$ to person $a_2$, while person $a_2$ gives letter $c_2$ to person $a_1$ at the same time.

If there are multiple solutions, print any.

对于每个测试用例，输出一个非负整数 $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$ 个人。

若存在多种解法，输出任意一种即可。