题目描述

小 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$，代表有 $n$ 个点，$m$ 条边，$k$ 个限制。

接下来 $m$ 行，第 $i$ 行代表第 $i$ 条边 $x,y$，方向是从 $x$ 到 $y$。

接下来 $k$ 行，每行有两个整数 $x,y$，代表限制。

输出格式

输出一个实数，最大的边数期望。

只要和标准答案误差小于 $10^{-2}$ 就认为是相同的。

样例输入

3 3 0
1 2
1 3
2 3

样例输出

2.0000000

数据规模与约定

保证图是有向无环的，保证对于每个限制 $(x,y)$，第 $x$ 条边和第 $y$ 条边的起点是相同的。可能有重边，限制可能重复。

对于每条边 $(x,y)$，保证 $1\le x,y\le n$。对于每个限制 $(x,y)$，保证 $1\le x,y\le m$。

$1 \le n \le 50$，$0 \le m \le 500$, $0 \le k \le 2000$。

题目来源

鸣谢 liuchenrui 提供 SPJ。