P7551 [COCI 2020/2021 #6] Alias

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`。

#### 样例 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](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T2 Alias_**。