4481 - [Jsoi2015]非诚勿扰

【故事背景】 JYY赶上了互联网创业的大潮，为非常勿扰开发了最新的手机App实现单身 大龄青年之间的“速配”。然而随着用户数量的增长，JYY发现现有速配的算法似 乎很难满足大家的要求，因此JYY决定请你来调查一下其中的原因。 【问题描述】 应用的后台一共有N个女性和M个男性，他们每个人都希望能够找到自己的 合适伴侣。为了方便，每个男性都被编上了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≤N,M≤500,000，0.4≤P<0.6

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