#P4501. 旅行
旅行
旅行
题目描述
小 C 来到了 F 国,小 C 想好好地参观 F 国。F 国可以看作一个有 个点 条边的有向无环图,小 C 刚开始站在 号点。假设现在小 C 站在 号点:
- 点 没有出边,结束旅游。
- 点 有 条出边,小 C 等概率地选一条边走过去。
小 J 是小 C 的好朋友,小 J 可以使用魔法让一些边消失,但是有一些限制 :如果删除第 条边,就必须删除第 条边。所有限制都必须满足。
现在小 J 想知道,在小 C 出发前删去若干条边,使小 C 经过的边数的期望最大。求这个最大期望。
输入格式
第一行三个整数,,代表有 个点, 条边, 个限制。
接下来 行,第 行代表第 条边 ,方向是从 到 。
接下来 行,每行有两个整数 ,代表限制。
输出格式
输出一个实数,表示经过的边数的最大期望。与正确答案的绝对误差小于 即可。
样例
3 3 0
1 2
1 3
2 3
2.0000000
数据规模与约定
保证图是有向无环的,保证对于每个限制 ,第 条边和第 条边的起点是相同的。可能有重边,限制可能重复。
对于每条边 ,保证 。对于每个限制 ,保证 。
,, 。