COCI 2020/2021 - Contest 6 - Alias

View as PDF

Submit solution

Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020-2021 / Contest 6
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Novak và Rafael đang chơi một biến thể đơn giản của trò chơi Alias. Novak cần làm cho Rafael đoán được một từ mà không cần phải nói ra từ đó. Rafael có ~n~ từ trong đầu anh ta, và có ~m~ liên kết giữa các từ với nhau. Một liên kết giữa từ ~x~ và ~y~ với thời gian ~t~ có nghĩa là nếu Rafael nhớ từ ~x~ hoặc nghe được nó, thì ~t~ miligiây sau anh ta sẽ nhớ được từ ~y~.

Novak và Rafael sẽ chơi ~q~ vòng. Ở mỗi vòng, Novak muốn biết: nếu anh ấy nói từ ~a~, sau bao lâu thì Rafael sẽ nhớ từ ~b~? Lưu ý: các vòng độc lập với nhau.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n, m \le 1000)~, số từ và số liên kết như trên. Mỗi dòng trong số ~m~ dòng tiếp theo chứa ~2~ từ ~x_{i}~ và ~y_{i}~ khác nhau và một số nguyên ~t_{i}~ ~(1 \le t_{i} \le 10^9)~ biểu diễn một kết nối như trên. Các từ có độ dài ~\le~ ~20~, và chỉ chứa các chữ cái in thường. Cả ~n~ từ sẽ xuất hiện ít nhất một lần. Có thể có nhiều kết nối giữa hai từ.

Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 1000)~ - số vòng. Mỗi dòng trong ~q~ dòng tiếp theo chứa hai từ ~a_{i}~ và ~b_{i}~ khác nhau - Novak nói từ ~a_{i}~ và Rafael cần nhớ từ ~b_{i}~. Cả hai từ nằm trong ~n~ từ trong đầu Rafael.

Output

In ra ~q~ dòng, dòng thứ ~i~ là thời gian (miligiây) để Rafael nhớ được từ cần nhớ ở vòng ~i~, hoặc "Roger" nếu Rafael không bao giờ nhớ được từ đó.

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

Giải thích ví dụ thứ nhất

Ở vòng đầu tiên, Novak sẽ nói từ "novak". Sau ~1~ miligiây, Rafael sẽ nhớ từ "goat", và sau ~4~ miligiây thì Rafael sẽ nhớ từ "simulator". Ở vòng thứ hai, Novak sẽ nói từ "simulator". Đây cũng là từ duy nhất Rafael nhớ được, do đó chúng ta in "Roger".

Subtask

  • ~50\%~ ~(5/10)~ số test có ~n \le 10~
  • ~20\%~ ~(2/10)~ số test tiếp theo có ~n \le 100~
  • ~30\%~ ~(3/10)~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.