COCI '20 Contest 6 #2 Alias

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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.

Input Specification

The first line contains integers n (2 \le n \le 1\,000) and m (1 \le m \le 1\,000), 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 \le t_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 1\,000), 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^\text{th} round. Both words appear in Rafael's database.

Output Specification

Output q lines. In the i^\text{th} line output the time for the i^\text{th} round in milliseconds, or Roger if Rafael will never remember the word.


1202 \le n \le 10
2202 \le n \le 100
330No additional constraints.

Sample Input 1

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

Sample Output 1


Explanation for Sample Output 1

In the first round, Novak will say the word novak. After 1 millisecond, Rafael will remember the word goat, and after 3 more milliseconds the required word simulator. In the second round, Novak will say the word simulator, but Rafael won't remember any other words.

Sample Input 2

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

Sample Output 2


Sample Input 3

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

Sample Output 3



There are no comments at the moment.