比赛场次	75
比赛名称	10101115
比赛状态	已结束比赛成绩
开始时间	2010-11-15 08:15:00
结束时间	2010-11-15 11:30:47
开放分组	全部用户
注释介绍

题目名称	最小密度路径
输入输出	`path.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	8 简单对比

用户	结果	时间	内存	得分
ZHZH	AAAAAAAAAA	0.000 s	0.00 MiB	100
王者自由	AAAAAAAAAA	0.000 s	0.00 MiB	100
郭乾乐	AAAAAAAATT	0.000 s	0.00 MiB	80
.Xmz	AWAAWWWWWT	0.000 s	0.00 MiB	30
ybh	WWAAWWWWWW	0.000 s	0.00 MiB	20
Pom	AWWWWWWWWT	0.000 s	0.00 MiB	10
reamb	AEWWEEEEEE	0.000 s	0.00 MiB	10
donny	AEWWEEEEEE	0.000 s	0.00 MiB	10
Citron酱	AEWWEEEEEE	0.000 s	0.00 MiB	10
magic	AWWWTTTTTT	0.000 s	0.00 MiB	10
wo shi 刘畅	AEWWEEEEEE	0.000 s	0.00 MiB	10
belong.zmx	AEWWEEEEEE	0.000 s	0.00 MiB	10
wangwangdog	WWWWWWWWWW	0.000 s	0.00 MiB	0
苏轼	WEWWEEEWWE	0.000 s	0.00 MiB	0
苏轼	WEWWEEEEEE	0.000 s	0.00 MiB	0
ZhouZn1	WEWWEEEEEE	0.000 s	0.00 MiB	0
Des.	WEWWEEEEEE	0.000 s	0.00 MiB	0
maxiem	WEWWEEEEEE	0.000 s	0.00 MiB	0
1102	WWWWWWWWWW	0.000 s	0.00 MiB	0
itachi	WWWWWWWTEE	0.000 s	0.00 MiB	0
Achilles	WWWWWWTTTT	0.000 s	0.00 MiB	0

最小密度路径

★★ 输入文件：path.in 输出文件：path.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

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

【输入格式】

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

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

再下一行有一个整数Q。

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

【输出格式】

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

【输入样例】

【输出样例】

5.000
5.500

【数据范围与约定】

对于60%的数据，有1 ≤ N ≤ 10，1 ≤ M ≤ 100，1 ≤ W≤ 1000，1 ≤ Q ≤ 1000；

对于100%的数据，有1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000。