Hurdle Jumping

Yeondu, who dreams of joining the national hurdle team, wants to practice hurdle jumping on a graph. The graph has N vertices and M edges. The edges are directed, so even if there is a path from 1 to 2, there may be no path from 2 to 1. A hurdle sits in the middle of each edge, and crossing an edge always requires jumping over its hurdle.

Yeondu will practice T times, and for each practice session the start vertex and end vertex are fixed in advance. To keep the practice from being too hard, for each session find a path from the start vertex to the end vertex that minimizes the height of the tallest hurdle on the path.

The first line gives three integers N, M, and T. The next M lines give the graph's edge information u, v, h, meaning there is an edge from u to v with a hurdle of height h in the middle of the edge. The last T lines give the practice sessions, one per line, as s and e. s is the start vertex and e is the end vertex.

For each practice session given in the input, print on its own line the minimum over all paths from the start vertex to the end vertex of the tallest hurdle height on the path. If the end vertex cannot be reached from the start vertex, print -1.

• 1 ≤ N ≤ 300
• 1 ≤ M ≤ 25,000
• 1 ≤ T ≤ 40,000
• 1 ≤ u, v ≤ N
• u ≠ v
• 1 ≤ h ≤ 1,000,000
• 1 ≤ s, e ≤ N
• s ≠ e