P13226 [GCJ 2015 #2] Bilingual

Elliot 的父母在家里用法语和英语与他交流。他听过很多单词，但并不总是清楚每个单词来自哪种语言！Elliot 确定有一句话是英语句子，有一句话是法语句子，还有一些其他句子可能是英语也可能是法语。如果一个单词出现在英语句子中，那么它一定是英语单词。如果一个单词出现在法语句子中，那么它一定是法语单词。 考虑 Elliot 听过的所有句子，问他听到的单词中，最少有多少个单词必须同时属于英语和法语单词？

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行包含一个整数 $N$。接下来的 $N$ 行，每行包含若干用空格分隔的“单词”。每个“单词”仅由小写字母 a-z 组成。前 $N$ 行中的第一行是确定为英语的句子，第二行是确定为法语的句子，其余的句子可能是英语也可能是法语。（注意，这些“单词”和“句子”不保证在任何真实语言中有效。）

对于每个测试用例，输出一行，格式为 “Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Elliot 听到的必须同时属于英语和法语的单词的最小数量。

**样例解释** 在第 1 个测试用例中，Elliot 确定第一句是英语，第二句是法语，因此没有歧义；唯一必须同时属于英语和法语的单词是 “baguettes”。 在第 2 个测试用例中，最后两句可以分别是：英语 英语、英语 法语、法语 英语、法语 法语。第二种分配方式可以最小化同时属于英语和法语的单词数量；最终这个集合是 d、e、i 和 j。 **数据范围** - $1 \leq T \leq 25$。 - 每个单词不超过 10 个字符。 - 两个“已知”句子各包含不超过 1000 个单词。 - “未知”句子各包含不超过 10 个单词。 **小数据范围** - 时间限制：5 秒。 - $2 \leq N \leq 20$。 **大数据范围** - 时间限制：10 秒。 - $2 \leq N \leq 200$。 由 ChatGPT 4.1 翻译