题目描述

世界上有 $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$ 个查询的答案列表，用空格分隔。

2
5 2
LIZZIE KEVIN BOHDAN LALIT RUOYU
1 2
1 3
2 2
KICK START
1 2
1 2

Case #1: 2 3
Case #2: -1 -1

提示

在样例 #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 完成