题目描述

Novak 和 Rafael 在玩一个猜单词的游戏。

Rafael 脑中有一个包含 $n$ 个单词的数据库。数据库中还有 $m$ 对形如 $x, y, t$ 的链接，表示如果他记起或听到了单词 $x$，他会在 $t$ 毫秒后记起单词 $y$。

游戏将进行 $q$ 轮，每轮游戏相互独立。每一轮游戏开始时，Novak 将说出初始单词 $a$。他想知道，多少毫秒后 Rafael 会记起目标单词 $b$？

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行每行两个字符串 $x_i, y_i$ 和一个整数 $t_i$，表示一对链接。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行两个字符串 $a_i, b_i$，表示第 $i$ 轮游戏中的初始单词和目标单词。

输出格式

共 $q$ 行，表示每轮游戏的答案。

如果 Rafael 能记起目标单词，输出一个整数，表示所需要的时间。否则，输出 Roger。

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

4
Roger

3 3
kile legend 4
legend beer 5
beer kile 6
2
kile beer
legend kile

9
11

4 5
rafael me 5
me ow 6
ow ausopenfinal 2012
ausopenfinal me 2
rafael ausopenfinal 2
3
rafael me
me rafael
ow me

4
Roger
2014

提示

样例 1 解释

第一轮游戏中，Novak 说出单词 novak。$1$ 毫秒后，Rafael 记起单词 goat。又过了 $3$ 毫秒，他记起目标单词 simulator。

第二轮游戏中，Novak 说出单词 simulator，但 Rafael 不会记起任何其他单词。

数据规模与约定

对于 $20$ 分的数据，$n \le 10$。
对于 $40$ 分的数据，$n \le 100$。
对于 $100\%$ 的数据，$2 \le n \le 10^3$，$1 \le m \le 10^3$，$1 \le t_i \le 10^9$，$1 \le q \le 10^3$。保证单词的长度不超过 $20$ 且仅含小写字母。

说明

本题分值按 COCI 原题设置，满分 $70$。

题目译自 COCI2020-2021 CONTEST #6 T2 Alias。