P7551 [COCI 2020/2021 #6] Alias

Novak and Rafael are playing a word guessing game. Rafael has a database in his mind that contains $n$ words. The database also has $m$ links of the form $x, y, t$, meaning that if he remembers or hears the word $x$, he will remember the word $y$ after $t$ milliseconds. The game will be played for $q$ rounds, and each round is independent. At the start of each round, Novak will say the initial word $a$. He wants to know: after how many milliseconds will Rafael remember the target word $b$?

The first line contains two integers $n, m$. The next $m$ lines each contain two strings $x_i, y_i$ and an integer $t_i$, representing a link. The next line contains an integer $q$. The next $q$ lines each contain two strings $a_i, b_i$, representing the initial word and the target word in the $i$-th round.

Output $q$ lines, the answer for each round. If Rafael can remember the target word, output an integer representing the required time. Otherwise, output `Roger`.

#### Explanation of Sample 1 In the first round, Novak says the word `novak`. After $1$ millisecond, Rafael remembers the word `goat`. After another $3$ milliseconds, he remembers the target word `simulator`. In the second round, Novak says the word `simulator`, but Rafael will not remember any other word. ------------ #### Constraints For the testdata worth $20$ points, $n \le 10$. For the testdata worth $40$ points, $n \le 100$. For $100\%$ of the testdata, $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$. It is guaranteed that each word has length at most $20$ and contains only lowercase letters. ------------ #### Notes **The score of this problem follows the original COCI settings, with a full score of $70$.**. **Translated from [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 ChatGPT 5