# cook your dish here
import sys
class Dijkstra:
def __init__(self, vertices):
# from 1 to v
self.V = (vertices + 1)
self.graph = [[0 for row in range(self.V)] for j in range(self.V)]
# print(len(self.graph), len(self.graph[0]))
def add_edge(self, src, dest, weight):
# directed graph
self.graph[src][dest] = weight
def minimum_distance(self, dist, visited):
min_dist = sys.maxsize
min_idx = None
for v in range(1, len(dist)):
if dist[v] < min_dist and visited[v] != True:
min_dist = dist[v]
min_idx = v
# print(min_idx)
return min_idx
def shortest_path(self, src):
dist = [sys.maxsize] * self.V
visited = [False] * self.V
dist[src] = 0
for _ in range(1, self.V):
# find minimum distance verte which is not visited yet
u = self.minimum_distance(dist, visited)
visited[u] = True
for v in range(1, self.V):
if self.graph[u][v] > 0 and visited[v] != True:
if self.graph[u][v] + dist[u] < dist[v]:
dist[v] = self.graph[u][v] + dist[u]
return dist
def path_length(self, src, dest):
dist = self.shortest_path(src)
return dist[dest]
# main method
t = int(input())
for _ in range(t):
V = None
while not V:
try:
V = int(input())
except:
V = None
continue
city = dict()
g = Dijkstra(V)
# print(V)
for i in range(1, V+1):
cname = input()
city[cname] = i
nedges = int(input())
for j in range(nedges):
v2, w = (int(x) for x in input().split())
g.add_edge(i, v2, w)
n = int(input())
for j in range(0, n):
c1, c2 = (input().split())
print(g.path_length(city[c1], city[c2]))
IyBjb29rIHlvdXIgZGlzaCBoZXJlCmltcG9ydCBzeXMKCmNsYXNzIERpamtzdHJhOgogICAgCiAgICBkZWYgX19pbml0X18oc2VsZiwgdmVydGljZXMpOgogICAgICAgICMgZnJvbSAxIHRvIHYKICAgICAgICBzZWxmLlYgPSAodmVydGljZXMgKyAxKQogICAgICAgIHNlbGYuZ3JhcGggPSBbWzAgZm9yIHJvdyBpbiByYW5nZShzZWxmLlYpXSBmb3IgaiBpbiByYW5nZShzZWxmLlYpXQogICAgICAgICMgcHJpbnQobGVuKHNlbGYuZ3JhcGgpLCBsZW4oc2VsZi5ncmFwaFswXSkpCiAgICAgICAgCiAgICBkZWYgYWRkX2VkZ2Uoc2VsZiwgc3JjLCBkZXN0LCB3ZWlnaHQpOgogICAgICAgICMgZGlyZWN0ZWQgZ3JhcGgKICAgICAgICBzZWxmLmdyYXBoW3NyY11bZGVzdF0gPSB3ZWlnaHQKICAgICAgICAKICAgIGRlZiBtaW5pbXVtX2Rpc3RhbmNlKHNlbGYsIGRpc3QsIHZpc2l0ZWQpOgogICAgICAgIG1pbl9kaXN0ID0gc3lzLm1heHNpemUKICAgICAgICBtaW5faWR4ID0gTm9uZQogICAgICAgIAogICAgICAgIGZvciB2IGluIHJhbmdlKDEsIGxlbihkaXN0KSk6CiAgICAgICAgICAgIGlmIGRpc3Rbdl0gPCBtaW5fZGlzdCBhbmQgdmlzaXRlZFt2XSAhPSBUcnVlOgogICAgICAgICAgICAgICAgbWluX2Rpc3QgPSBkaXN0W3ZdCiAgICAgICAgICAgICAgICBtaW5faWR4ID0gdgogICAgICAgICMgcHJpbnQobWluX2lkeCkKICAgICAgICByZXR1cm4gbWluX2lkeAogICAgICAgIAogICAgZGVmIHNob3J0ZXN0X3BhdGgoc2VsZiwgc3JjKToKICAgICAgICBkaXN0ID0gW3N5cy5tYXhzaXplXSAqIHNlbGYuVgogICAgICAgIHZpc2l0ZWQgPSBbRmFsc2VdICogc2VsZi5WCiAgICAgICAgCiAgICAgICAgZGlzdFtzcmNdID0gMAogICAgICAgIAogICAgICAgIGZvciBfIGluIHJhbmdlKDEsIHNlbGYuVik6CiAgICAgICAgICAgICMgZmluZCBtaW5pbXVtIGRpc3RhbmNlIHZlcnRlIHdoaWNoIGlzIG5vdCB2aXNpdGVkIHlldAogICAgICAgICAgICB1ID0gc2VsZi5taW5pbXVtX2Rpc3RhbmNlKGRpc3QsIHZpc2l0ZWQpCiAgICAgICAgICAgIHZpc2l0ZWRbdV0gPSBUcnVlCiAgICAgICAgICAgIAogICAgICAgICAgICBmb3IgdiBpbiByYW5nZSgxLCBzZWxmLlYpOgogICAgICAgICAgICAgICAgaWYgc2VsZi5ncmFwaFt1XVt2XSA+IDAgYW5kIHZpc2l0ZWRbdl0gIT0gVHJ1ZToKICAgICAgICAgICAgICAgICAgICBpZiBzZWxmLmdyYXBoW3VdW3ZdICsgZGlzdFt1XSA8IGRpc3Rbdl06CiAgICAgICAgICAgICAgICAgICAgICAgIGRpc3Rbdl0gPSBzZWxmLmdyYXBoW3VdW3ZdICsgZGlzdFt1XQogICAgICAgIAogICAgICAgIHJldHVybiBkaXN0CiAgICAgICAgCiAgICBkZWYgcGF0aF9sZW5ndGgoc2VsZiwgc3JjLCBkZXN0KToKICAgICAgICBkaXN0ID0gc2VsZi5zaG9ydGVzdF9wYXRoKHNyYykKICAgICAgICByZXR1cm4gZGlzdFtkZXN0XQogICAgICAgICAgICAKCgojIG1haW4gbWV0aG9kCnQgPSBpbnQoaW5wdXQoKSkKCmZvciBfIGluIHJhbmdlKHQpOgogICAgViA9IE5vbmUKICAgIAogICAgd2hpbGUgbm90IFY6CiAgICAgICAgdHJ5OgogICAgICAgICAgICBWID0gaW50KGlucHV0KCkpCiAgICAgICAgZXhjZXB0OgogICAgICAgICAgICBWID0gTm9uZQogICAgICAgICAgICBjb250aW51ZQogICAgICAgIAogICAgCiAgICBjaXR5ID0gZGljdCgpCiAgICBnID0gRGlqa3N0cmEoVikKICAgICMgcHJpbnQoVikKICAgIGZvciBpIGluIHJhbmdlKDEsIFYrMSk6CiAgICAgICAgY25hbWUgPSBpbnB1dCgpCiAgICAgICAgY2l0eVtjbmFtZV0gPSBpCiAgICAgICAgCiAgICAgICAgbmVkZ2VzID0gaW50KGlucHV0KCkpCiAgICAgICAgZm9yIGogaW4gcmFuZ2UobmVkZ2VzKToKICAgICAgICAgICAgdjIsIHcgPSAoaW50KHgpIGZvciB4IGluIGlucHV0KCkuc3BsaXQoKSkKICAgICAgICAgICAgCiAgICAgICAgICAgIGcuYWRkX2VkZ2UoaSwgdjIsIHcpCiAgICAKICAgIAogICAgbiA9IGludChpbnB1dCgpKQogICAgZm9yIGogaW4gcmFuZ2UoMCwgbik6CiAgICAgICAgYzEsIGMyID0gKGlucHV0KCkuc3BsaXQoKSkKICAgICAgICBwcmludChnLnBhdGhfbGVuZ3RoKGNpdHlbYzFdLCBjaXR5W2MyXSkpCiAKCiAgICA=
MQo0CmdkYW5zawoyCjIgMQozIDMKYnlkZ29zemN6CjMKMSAxCjMgMQo0IDQKdG9ydW4KMwoxIDMKMiAxCjQgMQp3YXJzemF3YQoyCjIgNAozIDEKMgpnZGFuc2sgd2Fyc3phd2EKYnlkZ29zemN6IHdhcnN6YXdh
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa