P3152 - 【nodgd又来造水题】统计逆序对

题目

P3152【nodgd又来造水题】统计逆序对

限制 : 时间限制 : 10000 MS 空间限制 : 65536 KB

评测说明 : 1s,256MB

给定1,2,...,n的一个排列，统计排列的逆序对数目是很简单的事情。
nodgd当然不希望问题过于简单，于是他只告诉你排列中的m个数，其他数是不确定的（即其他数随机排列）。你需要计算逆序对的期望值。

第一行两个数n,m。
接下来m行，每行两个数x,y，表示排列中的第x个数是y。保证不会自相矛盾。

一个实数，表示逆序对的期望值，保留8位小数。

样例输入1：
3 1
2 2

样例输入2：
5 0

样例输入3：
4 3
1 2
2 1
4 3

样例输入4：
4 2
2 4
3 1

样例输出1：
1.50000000

样例输出2：
5.00000000

样例输出3：
2.00000000

样例输出4：
3.50000000

1<=n<=500000
0<=m<n
注意精度