Description

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$?

Input Format

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 Format

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.

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

Hint

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 CONTEST #6 T2 Alias.

Translated by ChatGPT 5