Problem Description

Novak and Rafael are playing a word guessing game.

Rafael has a database containing $n$ words. The database also includes $m$ pairs of links in the form $x, y, t$, indicating 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, each round independent of the others. At the beginning of each round, Novak will say the initial word $a$. He wants to know how many milliseconds it will take for Rafael to remember the target word $b$.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two strings $x_i$ and $y_i$, and an integer $t_i$, representing a pair of links.

The next line contains an integer $q$.

The next $q$ lines each contain two strings $a_i$ and $b_i$, representing the initial and target words for the $i$-th round of the game.

Output Format

Output $q$ lines, each representing the answer for each round of the game.

If Rafael can remember the target word, output an integer representing the time required. Otherwise, output Roger.

Sample Input and Output

Sample Input #1

3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat

Sample Output #1

4
Roger

Sample Input #2

3 3
kile legend 4
legend beer 5
beer kile 6
2
kile beer
legend kile

Sample Output #2

9
11

Sample Input #3

4 5
rafael me 5
me ow 6
ow ausopenfinal 2012
ausopenfinal me 2
rafael ausopenfinal 2
3
rafael me
me rafael
ow me

Sample Output #3

4
Roger
2014

Notes

Sample 1 Explanation

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 does not remember any other words.

Data Size and Constraints

For $20$ points, $n \le 10$.
For $40$ points, $n \le 100$.
For $100\%$ of the data, $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$. The length of each word is guaranteed to be no more than $20$ and consists only of lowercase letters.

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $70$.

The problem is translated from COCI2020-2021 CONTEST #6 T2 Alias.

见题面 Input 部分

见题面 Output 部分