P13108 [GCJ 2019 #1A] Alien Rhyme

在一次外星探索中，你发现了外星诗歌的证据！你的语言学家团队确定，外星语言中的每个单词都有且只有一个字母带有重音；从重音字母开始到单词结尾的部分称为“重音后缀”。如果两个单词的重音后缀相同，则称这两个单词押韵。例如，单词 $\text{PROL}$ 和 $\text{TARPOL}$，如果它们的重音字母都是 $\text{o}$ 或 $\text{L}$，则它们押韵；但如果重音字母分别是 $\text{RS}$，或者 $\text{PROL}$ 的重音字母是 $\text{R}$ 而 $\text{TARPOL}$ 的重音字母是 $\text{P}$，又或者 $\text{PROL}$ 的重音字母是 $\text{O}$ 而 $\text{TARPOL}$ 的重音字母是 $\text{L}$，则它们不押韵。 你找回了一份包含 $N$ 个单词的列表，这些单词可能是外星诗歌的一部分。不幸的是，你并不知道每个单词的重音字母是哪一个。你可以选择丢弃零个或多个单词，对剩下的单词分配重音字母，然后将这些单词两两配对，使得每个单词只与它的配对单词押韵，并且不与其他配对中的单词押韵。 你想知道，最多能有多少个单词可以这样被配对。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $N$。接下来的 $N$ 行，每行包含一个由大写英文字母组成的字符串 $W_i$，表示一个不同的单词。注意，在不同的测试用例中，相同的单词可以有不同的重音分配方式。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足上述条件的最大单词数量。

**样例解释** 在样例 1 中，这两个单词可以通过合适的重音分配使其押韵，因此最大子集就是全部单词。 在样例 2 中，无论如何分配重音，都没有两个单词能押韵，因为任何两个后缀的最后一个字母都不同。因此最大子集为空，大小为 0。 在样例 3 中，如果将 `CODEJAM` 和 `JAM` 的重音都放在 `J` 上，将 `HAM` 和 `NALAM` 的重音都放在最后一个 `A` 上，将 `HUM` 和 `NOLOM` 的重音都放在 `M` 上，则可以使用全部单词。 在样例 4 中，任意两个单词都可以押韵，但总是通过把重音放在 `I` 上实现。因此，如果选取两个配对，来自不同配对的单词也会押韵。因此最多只能选取 2 个单词组成一个配对。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq W_i$ 的长度 $\leq 50$。 - $W_i$ 仅包含大写英文字母。 - 对于同一测试用例，$W_i \neq W_j$，即单词不重复。 **测试点 1（10 分，可见）** - $2 \leq N \leq 6$。 **测试点 2（27 分，隐藏）** - $2 \leq N \leq 1000$。 由 ChatGPT 4.1 翻译