Description

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

考虑 Elliot 听过的所有句子，问他听到的单词中，最少有多少个单词必须同时属于英语和法语单词？

Input Format

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

Output Format

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

4
2
he loves to eat baguettes
il aime manger des baguettes
4
a b c d e
f g h i j
a b c i j
f g h d e
4
he drove into a cul de sac
elle a conduit sa voiture
il a conduit dans un cul de sac
il mange pendant que il conduit sa voiture
6
adieu joie de vivre je ne regrette rien
adieu joie de vivre je ne regrette rien
a b c d e
f g h i j
a b c i j
f g h d e

Case #1: 1
Case #2: 4
Case #3: 3
Case #4: 8

Hint

样例解释

在第 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 翻译