P7551 [COCI 2020/2021 #6] Alias

Novak and Rafael are playing a simplified version of the game Alias. Novak needs to make Rafael guess a word without saying it. Rafael has a database of $n$ words in his head, and there are $m$ connections between some words. The connection between words $x$ and $y$, with time $t$, means that if Rafael remembers the word $x$ or hears it, after $t$ milliseconds he will remember the word $y$. Novak and Rafael will play $q$ rounds. In each round, Novak wants to know: if he says the word $a$, after how many milliseconds will Rafael remember the word $b$ for the first time? The rounds are independent.

The first line contains integers $n$ ($2 \leq n \leq 1000$) and $m$ ($1 \leq m \leq 1000$), the number of words and the number of connections. Each of the following $m$ lines contains two different words $x_i$ and $y_i$, and an integer $t_i$ ($1 \leq t_i \leq 10^9$), that describe a connection. The words consist of at most $20$ lowercase letters. All words from Rafael's database will appear at least once. It is possible that there are multiple connections between some pairs of words. The following line contains an integer $q$ ($1 \leq q \leq 1000$), the number of rounds. Each of the following $q$ lines contains two different words $a_i$ and $b_i$, the word that Novak will say and the word that Rafael needs to remember in the $i$-th round. Both words appear in Rafael's database.

Output $q$ lines. In the $i$-th line output the time for the $i$-th round in milliseconds, or `Roger` if Rafael will never remember the word.

#### Clarification of the first example: In the first round, Novak will say the word $\tt{novak}$. After $1$ millisecond, Rafael will remember the word $\tt{goat}$, and after $3$ more milliseconds the required word $\tt{simulator}$. In the second round, Novak will say the word $\tt{simulator}$, but Rafael won't remember any other words. ------------ #### Scoring In test cases worth 20 points, it holds $1 \leq n \leq 10$. In test cases worth additional 20 points, it holds $1 \leq m \leq 100$. ------------ #### Notes **The score of this problem follows the original COCI settings, with a full score of $70$.**. **From [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T2 Alias_**.