Minimum Fuel Capacity for Political Delegation

Indonesia has \( N \) cities numbered from \( 0 \) to \( N-1 \) and \( M \) bidirectional roads numbered from \( 0 \) to \( M-1 \). The \( i\)-th road connects city \( U[i] \) and city \( V[i] \) and consumes \( W[i] \) units of fuel when a car travels through it. It is guaranteed that any two cities are connected via some sequence of roads.

Over the next \( Q \) days, pairs of cities plan to establish political relations. Specifically, on day \( j \), city \( X[j] \) sends a delegate to city \( Y[j] \) by car, and city \( Y[j] \) sends a delegate to city \( X[j] \) by car. To avoid congestion, the two cars must never meet at the same time. In other words, they cannot be at the same city at the same time, and they must not traverse the same road in opposite directions at the same time. A car must traverse a road completely in one direction (i.e. it cannot reverse midway), but it may travel along the same road multiple times or wait at any city for an arbitrary amount of time.

Both cities want to minimize the required fuel capacity for their cars. Note that every city has an unlimited fuel supply, so the fuel capacity required is determined solely by the maximum fuel consumption (i.e. the maximum \( W \) value) among the roads used on the path. In other words, if a car uses a path whose roads have consumptions \( w_1, w_2, \ldots, w_k \), then its required fuel capacity is \( \max\{w_1, w_2, \ldots, w_k\} \). The goal for each query is to choose a route for each car such that they can schedule their journeys without conflict and to minimize the maximum required fuel capacity among the two cars.

With arbitrary waiting allowed, it turns out that the two cars can always avoid conflict if there exists a path from \( X[j] \) to \( Y[j] \) using only roads with consumption at most \( F \) (even if the two routes are identical, one car can wait to avoid meeting the other). Hence, the answer to each query is equal to the minimum \( F \) such that there exists a path from \( X[j] \) to \( Y[j] \) in the subgraph containing only roads with \( W \le F \). This is equivalent to the bottleneck shortest path problem. One can show that constructing the Minimum Spanning Tree (MST) of the graph and, for a given query, finding the maximum edge weight along the unique path in the MST between \( X[j] \) and \( Y[j] \) yields the optimal solution.

You are required to implement two functions:

• init(N, M, U, V, W) - Called once before all queries, where:
• \( N \) is the number of cities.
• \( M \) is the number of roads.
• \( U, V, W \) are arrays of length \( M \) representing the endpoints of each road and its fuel consumption.
• getMinimumFuelCapacity(X, Y) - Called \( Q \) times (once per query), where \( X \) and \( Y \) are the pair of cities wishing to establish political relations. It should return an integer representing the minimum required fuel capacity (i.e. the minimum possible maximum \( W \) on a path from \( X \) to \( Y \)) or \( -1 \) if no such path exists.

inputFormat

The input is given as follows:

N M
U[0] V[0] W[0]
U[1] V[1] W[1]
... (M lines in total)
Q
X[0] Y[0]
X[1] Y[1]
... (Q lines in total)

You should first call init(N, M, U, V, W) and then answer the Q queries using getMinimumFuelCapacity(X, Y).

outputFormat

For each query, output a single integer on a new line representing the minimum required fuel capacity. If no valid schedule exists, output \( -1 \) (though the graph is connected, so an answer always exists).

sample

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

4
4