P16778 [GKS 2020 #H] Friends

世界上有 $N$ 个人，编号为 $1$ 到 $N$。第 $i$ 个人有一个由大写英文字母组成的独特名字 $S_i$。 两个人是朋友，当且仅当存在至少一个字母，同时出现在两个人的名字中（该字母在各自名字中出现的位置不必相同）。毕竟，友谊需要共同点！ 从人 $A$ 到人 $B$ 的长度为 $n$ 的友谊链，是指一个序列 $X_1, X_2, \dots, X_n$，满足 $X_1 = A$，$X_n = B$，并且对于 $i = 1$ 到 $n-1$，$X_i$ 与 $X_{i+1}$ 是朋友。注意，任意两个人之间可能有零条或多条友谊链。 对于给定的 $Q$ 对人，你能找出他们之间最短友谊链的长度吗？如果两人之间不存在友谊链，则输出 $-1$。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$。第二行包含 $N$ 个字符串，即每个人的名字。第 $i$ 个字符串（从 $1$ 开始编号）为 $S_i$。随后 $Q$ 行，每行描述一个查询。第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$，表示名字列表中两个人的索引（从 $1$ 开始计数）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是按顺序给出的 $Q$ 个查询的答案列表，用空格分隔。

在样例 #1 中，共有 $2$ 个查询： - 第一个查询：LIZZIE 与 KEVIN 是朋友（因为他们的名字中都包含字母 E）。因此最短友谊链长度为 $2$。 - 第二个查询：LIZZIE 与 BOHDAN 不是直接朋友，但存在两条可能的最短友谊链（分别经由 KEVIN 或 LALIT）。因此最短友谊链长度为 $3$。注意，还存在其他更长的友谊链。 在样例 #2 中，共有 $2$ 个查询： - 第一个查询：KICK 与 START 之间没有友谊链连接。 - 第二个查询与第一个相同。注意，查询不一定互不相同。 ### 限制条件 $1 \le T \le 100$。 $1 \le Q \le 5 \times 10^4$。 对于所有 $i$，$S_i$ 由大写英文字母组成。 对于所有 $i$，$1 \le \text{len}(S_i) \le 20$。 所有 $S_i$ 互不相同。 对于所有 $i$，$1 \le X_i < Y_i \le N$。 **测试集 1** $2 \le N \le 100$。 **测试集 2** 最多 $10$ 个测试用例满足 $10^3 < N \le 5 \times 10^4$。 其余测试用例满足 $2 \le N \le 10^3$。 翻译由 DeepSeek V4 Pro 完成