UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4501. 旅行

Statistics 下载数据

Description

小C来到了F国,小C想好好地参观F国。F国可以看一个有n个点m条边的有向无环图,小C刚开始站在1号点。假设现在小C站在x号点:
1.点x没有出边,结束旅游。
2.点x有o条出边,小C等概率地选一条边走过去。
小J是小C的好朋友,小J可以使用魔法让一些边消失,但是有一些限制(x,y):第y条边如果被删掉了,那么第x条边也会受到影响,导致x条边被删掉。
现在小J想知道,如何删边使得小C所经过的边数期望最大。

Input

第一行三个整数,n,m,k(1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000),代表有n个点,m条边,k个限制。
接下来m行,第i行代表第i条边x,y(1 <= x, y <= n),方向是从x到y。
接下来k行,每行有两个整数x,y(1 <= x, y <= m),代表限制。
保证图是有向无环的,保证对于每个限制(x,y),第x条边和第y条边的起点是相同的。可能有重边,限制可能重复。
1 <= n <= 50, 0 <= m <= 500, 0 <= k <= 2000

Output

输出一个实数,最大的边数期望。只要和标准答案误差小于10^-2 就认为是相同的。

Sample Input

3 3 0
1 2
1 3
2 3

Sample Output

2.0000000

Hint

Source

鸣谢liuchenrui提供SPJ