Minimizing the Maximum Road in Two Disjoint Paths

The road network of a country is composed of \(n\) towns (numbered \(1\) to \(n\)) and \(m\) bidirectional roads connecting two different towns. Each road has a length (in kilometers). Recently, electric vehicles have become popular in this country. However, since charging stations exist only in towns, an electric vehicle must be able to travel entire roads on a single charge. In order to ensure that planned tourist trips are safe, officials want the longest road used in the trip to be as short as possible.

For a given trip, the tourism bureau picks a starting town \(u\) and a destination town \(v\) and then selects two paths from \(u\) to \(v\) such that the two paths do not share any roads (although they may share towns). The quality of the trip is measured by the maximum road length among all roads used in the two paths. The objective is to plan the trip so that this maximum road length is minimized. If it is impossible to find two such road–disjoint paths, output \(-1\).

For example, consider the following scenario. Suppose a part of the network is as illustrated below (the numbers on the nodes are town identifiers and the numbers on the edges are road lengths in kilometers):

Example 1: For towns \(1\) and \(2\), one might choose the paths:

1. \(1 \to 2\)
2. \(1 \to 3 \to 2\)

Suppose these paths use roads with lengths \(8\) and \(8,5\) respectively, then the maximum road length is \(8\). However, it might be possible to choose:

1. \(1 \to 2\)
2. \(1 \to 3 \to 5 \to 2\)

so that the maximum road length among all roads used is \(5\); this is optimal if no pair of disjoint paths exists with a maximum road shorter than \(5\). Note that the two paths are allowed to share towns as long as they do not share any roads.

Your task is: Given \(q\) queries, each specifying a pair of towns \(u\) and \(v\), determine for each query the minimum possible value of the longest road used in any valid pair of road–disjoint paths between \(u\) and \(v\), or output \(-1\) if such a pair does not exist.

Mathematical formulation:

Given an undirected graph \(G=(V,E)\) where \(V=\{1,2,\ldots,n\}\) and each edge \(e\in E\) has a length \(w_e\in \mathbb{N}\), for each query \((u,v)\) find the minimum \(L\) such that there exist two paths \(P_1\) and \(P_2\) from \(u\) to \(v\) that are edge-disjoint and for which \( \max\{w_e: e\in P_1 \cup P_2\} \le L\). If no such pair of paths exists, output \(-1\).

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (the number of towns and roads). Each of the next \(m\) lines contains three integers \(a\), \(b\), and \(w\) indicating there is a bidirectional road connecting town \(a\) and town \(b\) with length \(w\) kilometers. Following this, there is a line containing an integer \(q\), the number of queries. Each of the next \(q\) lines contains two integers \(u\) and \(v\) representing a query from town \(u\) to town \(v\>.

Constraints:

• \(1 \le n \le 10^5\) (or smaller depending on the test set)
• \(1 \le m \le 10^5\)
• \(1 \le w \le 10^9\)
• \(1 \le q \le 10^5\)

It is guaranteed that the input is such that a solution using an appropriate algorithm exists within the time limit.

outputFormat

For each query, output a single line containing the minimum possible value of the longest road used in any pair of road–disjoint \(u\) to \(v\) paths. If no such pair exists, output \(-1\).

sample

4 4
1 2 8
1 3 5
3 2 5
1 4 10
2
1 2
1 4

8
-1

</p>