8501: BZOJ4501：旅行

小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所经过的边数期望最大。

输入格式

第一行三个整数，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

输出格式

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

样例输入

3 3 0
1 2
1 3
2 3

样例输出

2.0000000

提示

没有写明提示

题目来源

鸣谢liuchenrui提供SPJ