#1848. 非诚勿扰

非诚勿扰

题目描述

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

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

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

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

这样,每个女性就有了自己接受的男性("如意郎君列表"为空的除外)。现在考虑任 意两个不同的、如意郎君列表非空的女性a\red{a}b,\red{b,}如果a\red{a}的编号比6\red{6}的编号小,而a\red{a}选择 的男性的编号比b\red{b}选择的编号大,那么女性a\red{a}和女性6\red{6}就叫做一对不稳定因素。

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

输入格式

输人第一行包含2\red{2}个自然数N,M,\red{N,M,}表示有N\red{N}个女性和N\red{N}个男性,以及所有女性的 "如意郎君列表"长度之和是M\red{M}

接下来一行一个实数P,\red{P,}为女性接受男性的概率。

接下来M\red{M}行,每行包含两个整数a,b,\red{a,b,}表示男性b\red{b}在女性a\red{a}的"如意郎君列表"中。

输人保证每个女性的"如意郎君列表"中的男性出现切仅出现一次。

输出格式

输出一行包含一个实数,四舍五人后保留到小数点后2\red{2}位,表示不稳定因素的期望数目。

样例

输入样例

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

输出样例

0.89

提示

对于30%\red{30\%}的数据满足:1\red{1≤}n,m\red{n,m≤}10,p=0.5\red{10,p=0.5}

对于60%\red{60\%}的数据满足:1\red{1≤}n,m\red{n,m≤}5000\red{5 000}

对于100%\red{100\%}的数据满足:1\red{1≤}n,m\red{n,m≤}500000,0.4\red{500000,0.4≤}p<0.6\red{p<0.6}