Word Cascade

Novak and Rafael are playing a word guessing game. Rafael has a database of \(n\) words and \(m\) directed links. Each link is represented as a triple \(x, y, t\), which means that if Rafael recalls or hears the word \(x\), he will recall the word \(y\) after \(t\) milliseconds.

The game will be played over \(q\) independent rounds. In each round, Novak says an initial word \(a\) and wonders how many milliseconds later Rafael will recall the target word \(b\). If it is impossible for Rafael to reach \(b\), output -1.

inputFormat

The first line contains three integers: \(n\), \(m\), and \(q\), which represent the number of words, the number of links, and the number of rounds respectively.

The next \(m\) lines each contain a word \(x\), a word \(y\), and an integer \(t\) representing a directed link from \(x\) to \(y\) with a delay of \(t\) milliseconds.

The following \(q\) lines each contain two words \(a\) and \(b\), representing the initial word and the target word of that round.

outputFormat

For each round, output a single line containing the minimum time (in milliseconds) by which Rafael will recall the target word \(b\) starting from \(a\), or -1 if it is impossible to recall the target word.

sample

3 3 3
apple banana 100
banana cherry 200
apple cherry 500
apple cherry
banana apple
apple banana

300
-1
100