82701 - 最小密度路径

给出一张有 N 个点 M 条边的加权有向无环图，接下来有 Q 个询问，每个询问包括 2 个节点 X 和 Y，要求算出从 X 到 Y 的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

第一行包括两个整数 N 和 M。

以下 M 行，每行三个数字 A,B,W，表示从 A 到 B 有一条权值为 W 的有向边。

再下一行有一个整数 Q。

以下 Q 行，每行一个询问 X 和 Y，如题意所诉。

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留 3 位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

1 \le N \le 50，1 \le M \le 1000，1\le W \le 10^5，1 \le Q \le 10^5

luogu