该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

Farmer John 想要和他的奶牛同伴们更好地交流，所以他决定学习哞语!

实际上哞语与英语非常相似，但是更加简约。单词只有四种类型：名词、及物动词、不及物动词和连词，每两个连续的单词之间必须用空格隔开。标点符号也只有两种类型：句号和逗号，当一个单词后面出现句号或逗号时，它会直接出现在该单词的后面，如果之后还有另一个单词，则标点符号后面再跟一个空格。

一条语句需要遵循以下格式之一：

• 类型1：名词 + 不及物动词。
• 类型2：名词 + 及物动词 + 名词。具体来说，及物动词后面必须至少有一个名词，并且除了第一个名词外，后面每个名词前面都必须有逗号。

如果在两个语句之间使用连词，就可以把它们连成一个复合句，由此产生的复合句不能与其他句或其他复合句进一步连接。每个语句（或两个语句连在一起的复合句）必须以句号结尾。

Farmer John 的单词库里面有 $N$ 个单词、 $C$ 个逗号和 $P$ 个句号（ $1 ≤ P, C ≤ N ≤ 1000$ ）。他可以使用一个单词或者标点符号的次数不能超过它们在单词库中出现的次数。请帮助他输出一个包含尽可能多的单词的语句序列。

本题中每个输入文件包含 $T$ （ $1 ≤ T ≤ 100$ ）组独立的测试用例。

输入格式（文件名：language.in）

第一行包含 $T$ ，表示测试用例的数量。每组测试用例按照如下方式进行说明：

第一行包含三个整数 $N$ 、 $C$ 和 $P$ 。

接下来 $N$ 行每行包含两个字符串。第一个字符串是 FJ 可以使用的单词（一个由最少 $1$ 个最多 $10$ 个小写字母组成的字符串），第二个字符串表示单词的类型，是下面任意一个： noun （名词）、 transitive-verb （及物动词）、 intransitive-verb （不及物动词）或者 conjunction （连词）。同一个单词在 FJ 的单词库中可能出现不止一次，但每次出现时它总是具有相同的类型。

输出格式（文件名：language.out）

第一行，输出最多可能的单词数量。

第二行，输出任意包含最多单词数量的语句序列。任意合法的序列都可以通过。

注意校验器对空格敏感，所以请确保不要输出任何多余的空格，尤其是在每行的末尾。

输入样例

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

输出样例

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

样例解释

对于第一个测试用例，唯一合法的序列就是空序列。对于接下来两个测试用例中的每一个，都可以使用单词库中除一个外的所有单词构建一个语句序列。

数据范围

测试点 $2 - 6$ 满足 $N \le 10$ 。

测试点 $7 - 11$ 满足 $N \le 100$ 。

测试点 $12 - 16$ 满足 $N \le 1000$ 。

模 $5$ 余 $2$ 的测试点满足没有及物动词。

模 $5$ 余 $3$ 的测试点满足没有不及物动词。

模 $5$ 余 $4$ 的测试点满足没有连词。

下载测试样例

1.in

1.out

5.in

5.out