问题 G: 营救教练计划

问题 G: 营救教练计划

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

第三次宇宙 ACM 大赛开战了。

创客由于 Winsoul 的泄密,导致教练被外星人 Hulin 绑架了。他被绑去了一个遥远的星球—— Yoyo星球。

从创客到 Yoyo星球只有一条路可以走。这条路长度总共为 n 。现在我们假设创客在 0 号位置,Yoyo星球在 n 号位置,你可以开着飞船从 0 飞到 1 ,再飞到 2 ,再飞到 3... 直到到 n 。

Amon 现在要去解救教练。可是飞船这么飞太慢了,等到了 Yoyo星球,教练等的黄花菜都凉了。所以 Amon 去找了邪恶又伟大的巫师帮助他。

巫师给了 Amon 两瓶药,一瓶随机药,一瓶传送药。他们分别有以下作用:

随机药:用完后的每次飞行,可以花和原本相同的时间,但是飞过 1、2、3、4、5、6  或 7 个地区。

也就是说,原本飞船在 第 i 号位置,可能会随机飞到 i+1,i+2,i+3,i+4,i+5,i+6 或 i+7 号位置,且只耗费 1 的时间。我们假设飞到每个位置的概率都相等。

传送药:在某些特定的位置,飞船可以直接从 x 号位置飞到 y 号位置,且不耗费任何时间。

Amon 一拿到药就把要用掉啦,并且立马前往 Yoyo星球。

注意,若 Amon 最后一次飞行,飞到了 n+1 或 n+2 或 ... n+6,我们也算他已经到达了终点哦~

我们假设每次的飞行时间为 1,请问 Amon飞到 Yoyo星球需要耗费的时间的数学期望是多少呢?



输入

本题有多组测试用例。

每组测试用例第一行有一个 n,代表 Yoyo星球的位置,和一个 m,代表跳跃点的个数。(1 ≤ n ≤ 100000,1 ≤ m ≤ 5000)。

接下来 m 行,每行一个 x 和一个 y (1 ≤ x,y ≤ n)(没有任意两个x相同)。

输出

输出 Amon 从创客到 Yoyo星球(大于等于n的位置)所需时间的数学期望(保留四位小数)。创客的位置始终为 0。

样例输入

3 0
6 2
2 4
5 6

样例输出

1.3061
1.6560
[提交][状态]