Problem1772--2021NHOI初中 第四题 记单词

1772: 2021NHOI初中 第四题 记单词

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

SubmitSolved: 1Submit Num: 1Statistics

Description

      农夫FJ和奶牛Bessie在玩单词游戏。Bessie脑海里总共有n个单词，而且有m个记忆关联，每个记忆关联的格式是：x、y、t，表示的意义是当Bessie记得单词x时，他只需要t微秒就能记起单词y。FJ和Bessie总共玩q轮游戏，每轮游戏开始时FJ都会给出两个单词u和v，表示的意义是：假如Bessie一开始记得单词u，那么Bessie至少需要多少微秒才能记起单词v？输出答案。每轮游戏都是相互独立的，互不影响。

Input

第一行，n和m。2<=n<=1000,  1<=m<=1000。

接下来有m行，每行格式是：x、y、t。其中x,y都是长度不超过20的单词，且全部由小写字母构成。对于单词x和y，可能存在多个记忆关联。

接下来一行是一个整数q。1<=q<=1000。

最后是q行，每行两个单词：u和v。

Output

共q行。每行对应一轮游戏的答案。如果该轮游戏Bessie无法完成任务，输出-1。

Sample Input Copy 

3 2 
novak goat 1 
goat simulator 3 
2 
novak simulator 
simulator goat

Sample Output Copy 

4
-1

HINT

输入/输出例子2
输入：
3 3 
kile legend 4 
legend beer 5 
beer kile 6 
2 
kile beer 
legend kile
输出：
9 
11
【部分数据】
对于40%的数据，n<=10。
对于80%的数据，n<=100。

Source/Category

2021年区赛 
Submit