Max Reliability Transmission

You are given a directed graph with n nodes and m edges. Each edge (u, v) has a reliability probability \( p \) (where \( 0 \le p \le 1 \)). The reliability of a path is the product of the reliabilities of its edges. For each query, given two nodes s and t, compute the maximum reliability of a packet being successfully transmitted from s to t.

If there is no path from s to t, the reliability is 0. Use the following formula for the reliability of a path if it goes through edges \( e_1, e_2, \dots, e_k \):

[ R = p_{e_1} \times p_{e_2} \times \cdots \times p_{e_k} ]

It is guaranteed that the input graph does not contain any negative probabilities. You are required to read from stdin and print the result to stdout.

inputFormat

The first line contains three integers n, m, and k where:

• n is the number of nodes.
• m is the number of directed edges.
• k is the number of queries.

The next m lines each contain two integers and a floating point number: u v p, representing an edge from u to v with a reliability probability p.

The following k lines each contain two integers: s t, representing a query to find the maximum reliability from node s to node t.

outputFormat

For each query, output a single line containing a floating point number which represents the maximum reliability from node s to node t. If there is no available path, output 0.

## sample

4 4 2
1 2 0.5
2 3 0.5
3 4 0.5
4 1 0.5
1 3
1 4

0.25
0.125

</p>