P7551 [COCI 2020/2021 #6] Alias

Novak 和 Rafael 正在玩一个简化版的《Alias》游戏。Novak 需要让 Rafael 猜出一个词，但不能直接说出这个词。Rafael 的头脑中有一个包含 $n$ 个单词的数据库，并且某些单词之间有 $m$ 条关联。单词 $x$ 和 $y$ 之间的关联带有时间 $t$，表示如果 Rafael 想起或听到了单词 $x$，那么在 $t$ 毫秒后他会想起单词 $y$。 Novak 和 Rafael 将进行 $q$ 轮游戏。在每一轮中，Novak 想知道：如果他说出单词 $a$，Rafael 将在多少毫秒后第一次想起单词 $b$？各轮游戏之间相互独立。

第一行包含两个整数 $n$（$2 \leq n \leq 1000$）和 $m$（$1 \leq m \leq 1000$），分别表示单词数量和关联数量。 接下来的 $m$ 行，每行描述一条关联，包含两个不同的单词 $x_i$ 和 $y_i$，以及一个整数 $t_i$（$1 \leq t_i \leq 10^9$）。单词由最多 $20$ 个小写字母组成。Rafael 数据库中的所有单词至少会出现一次。某些单词对之间可能存在多条关联。 下一行包含一个整数 $q$（$1 \leq q \leq 1000$），表示游戏轮数。 接下来的 $q$ 行，每行包含两个不同的单词 $a_i$ 和 $b_i$，分别表示第 $i$ 轮中 Novak 会说的单词，以及 Rafael 需要想起的单词。这两个单词都出现在 Rafael 的数据库中。

输出 $q$ 行。第 $i$ 行输出第 $i$ 轮所需的时间（单位为毫秒），如果 Rafael 永远无法想起该单词，则输出 `Roger`。

#### 样例 $1$ 解释： 在第一轮中，Novak 会说单词 $\tt{novak}$。$1$ 毫秒后，Rafael 会想起单词 $\tt{goat}$，再过 $3$ 毫秒后，他会想起目标单词 $\tt{simulator}$。在第二轮中，Novak 会说单词 $\tt{simulator}$，但 Rafael 不会再想起任何其他单词。 ------------ #### 数据规模与约定 在 $20$ 分的测试数据中，满足 $1 \leq n \leq 10$。 在另外 $20$ 分的测试数据中，满足 $1 \leq m \leq 100$。 ------------ #### 说明 **本题分值按 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_**。 Translated by DeepSeek-V3