题目描述

敌人已经侵入了你的宇宙飞船，唯有高超的战术才能让你抵御外敌！为了在飞船中移动，你的士兵将使用两种设备：传送器和涡轮电梯。

传送器允许士兵在房间之间瞬间移动。每个房间都有一个传送器，并且房间有颜色编码：如果一名士兵身处具有某种颜色的房间，她就可以利用该房间的传送器立即移动到任何其他具有相同颜色的房间。

涡轮电梯则让士兵以较慢的速度在房间之间移动。涡轮电梯就像可以在多个方向上移动的电梯。每个涡轮电梯从一个房间移动到另一个房间，并且需要一定的时间。关于涡轮电梯的注意事项：

• 涡轮电梯不是双向的：如果一个涡轮电梯能将士兵从房间 $a$ 运送到房间 $b$，同一个涡轮电梯并不能将士兵从房间 $b$ 运送到房间 $a$，尽管可能存在另一个涡轮电梯能完成此事。
• 多名士兵可以使用同一个涡轮电梯，并且彼此之间不会产生任何干扰。

你将获得若干士兵的位置与目的地。对于每位士兵，请输出她从其位置到达目的地所需的最短时间。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。

对于每个测试用例：

每个测试用例的第一行包含一个整数 $N$，表示飞船中房间的数量。房间编号从 $1$ 到 $N$。接下来的 $N$ 行，每行包含一个表示房间颜色的字符串，从房间 $1$ 到房间 $N$。字符串只包含小写英文字母 a–z 和数字 $0$–$9$，且每个字符串的长度不超过 $2$。

测试用例的下一行是一个整数 $M$，表示飞船中涡轮电梯的数量。接下来的 $M$ 行，每行包含 $3$ 个由空格分隔的整数 $\text{a}_i$, $\text{b}_i$, $\text{t}_i$，告诉我们存在一个涡轮电梯，可以在 $\text{t}_i$ 秒内将士兵从房间 $\text{a}_i$ 运送到房间 $\text{b}_i$。

测试用例的下一行包含一个整数 $S$，表示你指挥的士兵数量。接下来的 $S$ 行，每行包含两个整数：一位士兵的位置和目的地 $\text{p}_j$ 和 $\text{q}_j$。

输出格式

对于每个测试用例，输出一行仅包含字符串 “Case #x:”，其中 $x$ 是测试用例编号（从 $1$ 开始）。在接下来的 $S$ 行中，每行输出一个整数：在第 $j$ 行，输出一名士兵从 $\text{p}_j$ 到达 $\text{q}_j$ 所需的最少秒数。如果不存在从 $\text{p}_j$ 到 $\text{q}_j$ 的路径，则输出的整数应为 $-1$。

3
3
gl
t3
t3
3
1 2 217
3 2 567
1 1 21
2
2 1
2 3
4
ca
bl
bl
8z
0
3
1 2
2 3
1 1
8
re
b7
ye
gr
0l
0l
ye
b7
7
4 1 19
2 4 21
2 5 317
4 5 34
4 7 3
4 8 265
8 6 71
3
4 3
2 6
1 4

Case #1:
-1
0
Case #2:
-1
0
0
Case #3:
3
55
-1

提示

限制

• $1 \le S \le 100$。
• $1 \le a_i, b_i \le N$。
• $0 \le t_i \le 1000$。
• $1 \le p_j, q_j \le N$。

测试集 1 - 可见

• $1 \le T \le 10$。
• $1 \le N \le 1000$。
• $0 \le M \le 3000$。

测试集 2 - 隐藏

• $T = 1$。
• $1 \le N \le 80000$。
• $0 \le M \le 3000$。

翻译由 DeepSeek V4 Pro 完成