题目背景

Farmer John is interested in better interacting with his fellow cows, so he decided he will learn the moo language!

题目描述

Moo language is actually quite similar to English, but more minimalistic. There are only four types of words: nouns, transitive verbs, intransitive verbs, and conjunctions. Every two consecutive words must be separated by a space. There are also only two types of punctuation: periods and commas. When a period or comma appears after a word, it appears directly after the word, and is then followed by a space if another word appears next.

A sentence needs to follow one of the following formats:

• Type 1: noun + intransitive verb.
• Type 2: noun + transitive verb + noun(s). Specifically, at least one noun must follow the transitive verb, and there must be a comma in front of every following noun besides the first following noun.

Two sentences may be joined into a compound sentence if a conjunction is placed in between them. The resulting compound sentence cannot be further joined with other sentences or other compound sentences. Every sentence (or compound sentence, if two sentences are joined) must end with a period.

Farmer John has a word bank of $N$ words, $C$ commas, and $P$ periods. He may only use a word or punctuation mark as many times as it appears in the word bank. Help him output a sequence of sentences containing the maximum possible number of words.

Each input file contains $T$ independent instances of this problem.

输入格式

The first line contains $T$, the number of instances. Each instance is specified as follows:

The first line consists of three integers $N, C$ and $P$.

The $N$ following lines will consist of two strings. The first string will be the word itself that FJ can use (a string of at least $1$ and at most $10$ lowercase letters), and the second string will be either one of the following: noun, transitive-verb, intransitive-verb, or conjunction, denoting the type of the word. It is possible the same word occurs more than once in FJ's word bank, but it will always have the same type each time it appears.

输出格式

In the first line, output the maximum possible number of words.

In the second line, output any sequence of sentences with the maximum possible number of words. Any valid sequence will be accepted.

The grader is sensitive to whitespace, so make sure not to output any extraneous spaces, particularly at the end of each line.

题目大意

题目背景

FJ 对与奶牛更好地互动感兴趣，所以他决定学习 moo 语言！

题目描述

moo 语言与英语相似，但更为简单。单词只有四种类型：名词、及物动词、不及物动词和连词，每两个单词之间必须用空格隔开。标点符号仅包含逗号和句号，它会跟在单词后面，若该标点符号后面存在单词，则需要隔一个空格再放单词。

对于每个句子，都需要遵循以下格式中的一条：

1. 名词+不及物动词。
2. 名词+及物动词+名词（可以有多个）。及物动词后面必须有至少一个名词。除及物动词后面的第一个名词外，后面的每个名词前面都必须加一个逗号。

也可以在两个句子之间加一个连词，形成复合句，复合句不能与其他句子用连词连接。每一个句子（包括复合句）都必须以句号结尾。

FJ 的词库中有 $N$ 个单词、$C$ 个逗号和 $P$ 个句号。每个单词的使用次数不能超过这个单词在词库中出现的次数。现在，你要帮他输出几个符合以上要求的句子，使总单词数尽量多。

每个输入文件中共包含 $T$ 组样例。

输入格式

第一行输入 $T$，表示样例组数。对于每组样例，格式如下：

第一行输入三个正整数 $N$、$C$ 和 $P$。

在接下来的 $N$ 行，每行输入两个字符串。第一个字符串输入一个 FJ 可以用的单词（全为小写字母，长度为 $1$ 至 $10$），第二个字符串为以下字符串中的任意一个，表示该单词的类型：

• noun（名词）；
• transitive-verb（及物动词）；
• intransitive-verb（不及物动词）；
• conjunction（连词）。

同一个单词可能在词库中出现多次，但是每次出现时它们的类型都相同。

输出格式

第一行输出组成符合以上要求的句子序列的最大单词数。

在第二行中，输出句子序列，使单词数最多。本题开启 SPJ，任何符合以上要求的句子序列均可通过。

请不要输出多余的空格，尤其是在每行末尾。

translated by liyuanchen2021

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.

提示

$1\le T\le 100$，$1 \leq P,C\le N \leq 10^3$.

• Inputs 2-6: $N\le 10$.
• Inputs 7-11: $N\le 100$.
• Inputs 12-16: $N\le 1000$.
• Inputs with remainder 2 when divided by 5: There are no transitive verbs.
• Inputs with remainder 3 when divided by 5: There are no intransitive verbs.
• Inputs with remainder 4 when divided by 5: There are no conjunctions.