CF1784B.Letter Exchange
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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'.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤104 ). The description of the test cases follows.
The first line of each test case contains a single integer m ( 2≤m≤105 ) — the number of people.
The i -th of the next m lines contains a string si 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 105 .
输出格式
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 a1 c1 a2 c2 , describing the exchanges in chronological order ( 1≤a1,a2≤m ; a1=a2 ; c1,c2 are one of {w,i,n} ): person a1 gives letter c1 to person a2 , while person a2 gives letter c2 to person a1 at the same time.
If there are multiple solutions, print any.
输入输出样例
输入#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