P13454 [GCJ 2008 Qualification] Saving the Universe

有一个都市传说：如果你在 Google 首页搜索“Google”，宇宙就会崩溃。我们有个秘密要告诉你……这是真的！请不要尝试，也不要告诉别人。好吧，其实不是，我们只是开玩笑。 但在遥远的另一个宇宙中，情况却并非如此。在那个宇宙里，如果你在任何搜索引擎上搜索该搜索引擎的名字，宇宙真的会崩溃！ 为了解决这个问题，人们想出了一个有趣的办法。所有的查询会被集中到一起，然后交给一个中央系统来决定每个查询由哪个搜索引擎处理。中央系统会将一系列查询发送给某个搜索引擎，并且可以随时切换到另一个搜索引擎。所有查询必须按照收到的顺序处理。中央系统绝不能将一个查询发送给名字与该查询相同的搜索引擎。为了降低成本，切换搜索引擎的次数应尽量少。 你的任务是：假设我们以最优方式编程，请你告诉我们中央系统需要切换多少次搜索引擎。

输入文件的第一行包含测试用例数 $N$。接下来有 $N$ 组测试数据。 每组测试数据首先包含一个整数 $S$，表示搜索引擎的数量。接下来的 $S$ 行，每行包含一个搜索引擎的名字。每个搜索引擎名字不超过一百个字符，只包含大写字母、小写字母、空格和数字。不会有两个搜索引擎名字相同。 接下来一行包含一个整数 $Q$，表示收到的查询数量。接下来的 $Q$ 行，每行包含一个查询。每个查询都是本组测试数据中某个搜索引擎的名字。

对于每组输入数据，输出： Case #$X$: $Y$ 其中 $X$ 是测试用例编号，$Y$ 是切换搜索引擎的次数。初始选择搜索引擎不计为一次切换。

**样例解释** 在第一个测试用例中，一种可行的方案是先使用 Dont Ask，在第 8 个查询后切换到 NSM。 在第二个测试用例中，你可以一直使用 B9，无需切换。 **数据范围** - $0 < N \leq 20$ **小数据集（5 分，测试点 1 - 可见）** - $2 \leq S \leq 10$ - $0 \leq Q \leq 100$ **大数据集（20 分，测试点 2 - 隐藏）** - $2 \leq S \leq 100$ - $0 \leq Q \leq 1000$ 由 ChatGPT 4.1 翻译