Minimum Density Path in a Weighted DAG

You are given a weighted directed acyclic graph (DAG) with N nodes and M edges. Each edge has an associated weight. Then, you are given Q queries; in each query, two nodes X and Y are specified. Your task is to find a path from X to Y such that the density is minimized.

The density of a path is defined as:

[ \text{density} = \frac{\text{sum of edge weights on the path}}{\text{number of edges in the path}} ]

If there is no path from X to Y, output -1.

inputFormat

The first line contains two integers N and M, the number of nodes and edges respectively.

The next M lines each contain three integers U V W, representing a directed edge from node U to node V with weight W.

The next line contains an integer Q, the number of queries.

Each of the following Q lines contains two integers X and Y, representing a query to find the minimum density path from node X to node Y.

outputFormat

For each query, print a single line with the minimum density of a path from X to Y formatted to six decimal places. If no path exists, print -1.

sample

4 4
1 2 1
2 3 3
1 3 5
3 4 2
3
1 3
1 4
2 4

2.000000
2.000000
2.500000