Description

Given a weighted directed acyclic graph (DAG) with $N$ vertices and $M$ edges, followed by $Q$ queries. Each query consists of two vertices $X$ and $Y$. Compute a path from $X$ to $Y$ with minimum density, where density is defined as the sum of edge weights along the path divided by the number of edges.

Input Format

The first line contains two integers $N$ and $M$. Each of the next $M$ lines contains three integers $A, B, W$, indicating there is a directed edge from $A$ to $B$ with weight $W$. The next line contains an integer $Q$. Each of the next $Q$ lines contains a query with two vertices $X$ and $Y$, as described.

Output Format

For each query, output one line containing the density of the minimum-density path, rounded to $3$ decimal places. If no such path exists, output OMG!.

3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3

5.000
5.500

Hint

Constraints

$1 \le N \le 50$, $1 \le M \le 1000$, $1 \le W \le 10^5$, $1 \le Q \le 10^5$.

Translated by ChatGPT 5