Taco Bottleneck Times

A large company has a central server that connects all of its computers. The network is modeled as an undirected graph with N nodes (computers) and M edges (direct connections). Each connection between two computers has an associated transfer time given in milliseconds.

When a message is sent from one computer to another, it is routed along the path with the fewest hops. The bottleneck time for that path is defined as the maximum transfer time of all the connections along the path, i.e. $$\max\{t_i\}$$ where each \(t_i\) represents the transfer time on an edge along the chosen route.

You are given Q queries. For each query, compute the bottleneck time for the message between the given pair of computers using a breadth-first search (BFS) based routing. If the two computers are not connected, output -1.

inputFormat

The input is given from stdin as follows:

N M
u1 v1 t1
u2 v2 t2
... (M lines)
Q
s1 d1
s2 d2
... (Q lines)

Here, the first line contains two integers \(N\) and \(M\), where \(N\) is the number of computers and \(M\) is the number of connections. Each of the following M lines contains three integers \(u\), \(v\), and \(t\), indicating a bidirectional connection between nodes \(u\) and \(v\) with a transfer time of \(t\) milliseconds. The next line contains an integer \(Q\), and the following Q lines each contain two integers representing a query for the source and destination nodes.

outputFormat

For each query, output the bottleneck time on a separate line. If the source and destination nodes are not connected, output -1.

## sample

5 6
1 2 4
2 3 2
1 3 6
3 4 3
4 5 5
2 5 7
3
1 4
2 5
3 1

6
7
6

</p>