Exchange Rate Calculator

You are given n kingdoms, which are consecutively labeled starting from 'A'. There are m directed exchange rates between these kingdoms. Each exchange rate is provided as a directed edge from one kingdom to another along with a conversion rate. The conversion cost along a path is the product of the exchange rates along the path. Your task is to determine the minimum conversion rate (i.e. the smallest product) from a source kingdom to a destination kingdom for several queries.

If there is no valid conversion path between the specified kingdoms, output -1. Note that for a query where the source and destination are the same kingdom, the answer is 1.0, even if no explicit self-conversion rate is provided.

The rate calculations follow the formula:

[ d(u,v)=\min_{\text{all paths }p\ from\ u\ to\ v}\prod_{(i,j)\in p} r(i,j) ]

where \( r(i,j) \) represents the direct exchange rate from kingdom \( i \) to kingdom \( j \). Use the Floyd–Warshall algorithm or any appropriate algorithm to compute these values.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
u1 v1 r1
u2 v2 r2
... (m lines in total)
q
s1 t1
s2 t2
... (q lines in total)

Here:

• n is the number of kingdoms. They are labeled from 'A' to 'A' + n - 1.
• m is the number of direct exchange rates.
• Each of the next m lines contains a source kingdom u, a destination kingdom v, and a floating point number r representing the exchange rate from u to v.
• q is the number of queries.
• Each of the next q lines contains two kingdoms: a source s and a destination t.

outputFormat

For each query, print the computed minimum exchange rate from the source kingdom to the destination kingdom on a separate line. If there is no valid conversion path, print -1.

## sample

5 6
A B 1.2
B C 1.3
C D 0.9
D E 1.4
E A 0.8
B D 1.1
3
A D
C E
A F

1.32
1.26
-1

</p>