Minimize the Maximum Hurdle

Farmer John wants the cows to prepare for the county jumping competition. Bessie and the gang are practicing jumping over hurdles. Since high hurdles are exhausting, the cows care only about the height of the tallest hurdle on their path.

The training room has \(N\) stations, numbered \(1, \dots, N\). There are \(M\) one-way paths; the \(i\)th path goes from station \(S_i\) to station \(E_i\) and has exactly one hurdle with height \(H_i\). The cows have \(T\) tasks where each task consists of two distinct numbers \(A_i\) and \(B_i\). For each task, a cow must travel from station \(A_i\) to station \(B_i\) (possibly passing through other stations) while trying to minimize the maximum hurdle height encountered along the route.

Your task is to compute, for each query, the minimum possible value of the highest hurdle in any valid route from \(A_i\) to \(B_i\). If no such path exists, output -1.

inputFormat

The first line contains three integers \(N, M, T\) separated by spaces.

The next \(M\) lines each contain three integers \(S_i\), \(E_i\), and \(H_i\), representing a one-way path from station \(S_i\) to station \(E_i\) with a hurdle of height \(H_i\).

The next \(T\) lines each contain two integers \(A_i\) and \(B_i\), indicating that the cow needs to travel from station \(A_i\) to station \(B_i\).

outputFormat

Output \(T\) lines. The \(i\)th line should contain a single integer, the minimum possible maximum hurdle height on any path from \(A_i\) to \(B_i\). If no such path exists, output -1.

sample

4 4 2
1 2 3
2 3 4
3 4 2
1 4 10
1 4
2 4

4
4