3986: 匹配交错 cross
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：1
题目描述
左边有N个点从上到下编号为1到N。右边也有N个点从上到下编号为1到N。
每一个左边点有一个可链接右边点的列表。
左边点按编号从小到大开始尝试链接，有p的概率链接成功，失败后尝试链接下一个点，循环列表直到成功。
问会出现的交错数的期望。
例子
左1链接右3
左2链接右3
左3链接右1
交错数为2
每一个左边点有一个可链接右边点的列表。
左边点按编号从小到大开始尝试链接，有p的概率链接成功，失败后尝试链接下一个点，循环列表直到成功。
问会出现的交错数的期望。
例子
左1链接右3
左2链接右3
左3链接右1
交错数为2
输入格式
输入第一行两个自然数n，m，表示有n个点对，列表总长m
第二行一个实数p为成功链接概率
接下来m行，每行两个整数a，b，表示a的列表里有b
保证左边点的列表不会有重复右边点
1<=n,m<=500000,0.4<=p<0.6
第二行一个实数p为成功链接概率
接下来m行，每行两个整数a，b，表示a的列表里有b
保证左边点的列表不会有重复右边点
1<=n,m<=500000,0.4<=p<0.6
输出格式
输出一个实数，表示出现交错数的期望，保留小数点后两位。
输入样例 复制
5 5
0.5
5 1
3 2
2 2
2 1
3 1输出样例 复制
0.89