Description

这次就不编故事了，直接进入主题。

A线： 1 2 3.....

B线： 1 2 3 .....

如上图，存在两条平行线，每条平行线上都标有N个点，标号为1到N，现在可以在A线和B线分别选两个点进行连线，所选的点必须是前面没有选过的点，就这样进行下去，可能会产生两个线段相交，产生交点。我的问题就是，假如已经进行了一些连线，还有一些点没有被连接，现在你可以随机选取还没有被选择的点进行连接，请你求出产生交点的个数的期望。 PS：题目描述的实在有点儿搓，请看样例解释，应该就会明白的题目的意思了。

Input

第一行，给出两个整数N和M，2<=N<=10000，1<=M<=50，分别表示每条线上有N个点，每条线上有M个点已经被选了； 接下来有M行，每行有两个整数S和E，1<=S,E<=N，表示A线上的S点和B线上的E点已经相连。

Output

输出一个整数，表示交点个数的期望，结果保留一位小数。

Sample

Input

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

Output

1.5
1.5
1.0

Hint

样例一： 每条线上有3个点，有1对点相连，即A线上的2点和B线上的3点相连，那还有4个空闲点，他们相连的情况有两种： 情况1，A线上的1点和B线上的1点相连；A线上的3点和B线上的2点相连，此时产生了一个交点；情况2，A线上的1点和B线上的2点相连；A线上的3点和B线上的1点相连，此时产生了两个交点。 因此在两种情况下共产生了3个交点，所以结果为3/2=1.5 样例二： 可以做相同的解释，每条线上4个点，也是有一对点相连，A线上的1点和B线上的1点，那剩下的6个点，总共有6种连接情况，产生9个交点（画一下图就知道了），所以交点的期望为9/6=1.5 样例三不解释了，一看就明白^_^