[JSOI2015] 非诚勿扰

题目背景

JYY 赶上了互联网创业的大潮，为非诚勿扰开发了最新的手机 App 实现单身大龄青年之间的“速配”。然而随着用户数量的增长，JYY 发现现有速配的算法似乎很难满足大家的要求，因此 JYY 决定请你来调查一下其中的原因。

题目描述

应用的后台一共有 $N$ 个女性和 $N$ 个男性，他们每个人都希望能够找到自己的合适伴侣。为了方便，每个男性都被编上了 $1$ 到 $N$ 之间的一个号码，并且任意两个人的号码不一样。每个女性也被如此编号。

JYY 应用的最大特点是赋予女性较高的选择权，让每个女性指定自己的“如意郎君列表”。每个女性的如意郎君列表都是所有男性的一个子集，并且可能为空。如果列表非空，她们会在其中选择一个男性作为自己最终接受的对象。

JYY 用如下算法来为每个女性速配最终接受的男性：将“如意郎君列表”中的男性按照编号从小到大的顺序呈现给她。对于每次呈现，她将独立地以 $P$ 的概率接受这个男性（换言之，会以 $1-P$ 的概率拒绝这个男性）。如果她选择了拒绝，App 就会呈现列表中下一个男性，以此类推。如果列表中所有的男性都已经呈现，那么中介所会重新按照列表的顺序来呈现这些男性，直到她接受了某个男性为止。显然，在这种规则下，每个女性只能选择接受一个男性，而一个男性可能被多个女性所接受。当然，也可能有部分男性不被任何一个女性接受。

这样，每个女性就有了自己接受的男性（“如意郎君列表”为空的除外）。现在考虑任意两个不同的、如意郎君列表非空的女性 $a$ 和 $b$，如果 $a$ 的编号比 $b$ 的编号小，而 $a$ 选择的男性的编号比 $b$ 选择的编号大，那么女性 $a$ 和女性 $b$ 就叫做一对不稳定因素。

由于每个女性选择的男性是有一定的随机性的，所以不稳定因素的数目也是有一定随机性的。JYY 希望你能够求得不稳定因素的期望个数（即平均数目），从而进一步研究为什么速配算法不能满足大家的需求。

输入格式

输入第一行包含 $2$ 个自然数 $N,M$，表示有 $N$ 个女性和 $N$ 个男性，以及所有女性的“如意郎君列表”长度之和是 $M$。

接下来一行一个实数 $P$，为女性接受男性的概率。

接下来 $M$ 行，每行包含两个整数 $a,b$，表示男性 $b$ 在女性 $a$ 的“如意郎君列表”中。

输出格式

输出 $1$ 行，包含一个实数，四舍五入后保留到小数点后 $2$ 位，表示不稳定因素的期望数目。

样例 #1

样例输入 #1

5 5
0.5
5 1
3 2
2 2
2 1
3 1

样例输出 #1

0.89

提示

对于 $100\%$ 的数据，$1\leq N,M\leq 5\times 10^5$，$0.4\leq P<0.6$。

输入保证每个女性的“如意郎君列表”中的男性出现且仅出现一次。