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.

In test cases worth 20 points, it holds \(1 \le n \le 10\).
In test cases worth additional 20 points, it holds \(1 \le n \le 100\).

The first line contains integers \(n\) (\(2 \le n \le 1000\)) and \(m\) (\(1 \le m \le 1000\)), the number of words and the
number of connections.
Each of the following \(m\) lines contains two different words \(x@@RISE_MATH_BLOCK_0@@i\), and an integer \(t@@RISE_MATH_BLOCK_1@@i \le 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 \le q \le 1000\)), the number of rounds.
Each of the following \(q\) lines contains two different words \(a@@RISE_MATH_BLOCK_2@@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.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 6