题目描述

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。

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 会说单词 $\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 CONTEST #6 T2 Alias。

Translated by DeepSeek-V3