1517：间谍网络

题目描述

由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果 $A$ 间谍手中掌握着关于 $B$ 间谍的犯罪证据，则称 $A$ 可以揭发 $B$。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 $n$ 个间谍，每个间谍分别用 $1$ 到 $n$ 的整数来标识。

请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

输入格式

第一行只有一个整数 $n$。

第二行是整数 $p$。表示愿意被收买的人数。

接下来的 $p$ 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。

紧跟着一行只有一个整数 $r$。

然后 $r$ 行，每行两个正整数，表示数对 $(A, B)$，$A$ 间谍掌握 $B$ 间谍的证据（即 $A$ 可以揭发 $B$）。

输出格式

如果可以控制所有间谍，第一行输出 YES，并在第二行输出所需要支付的贿金最小值。否则输出 NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

样例

样例输入 #1

2
1
2 512
2
1 2
2 1

样例输出 #1

YES
512

样例解释 #1

• 间谍总数 $n=2$。
• 愿意被收买的人数 $p=1$：间谍 $2$ 可以被收买，费用 $512$。
• 揭发关系 $r=2$：
  • 间谍 $1$ 掌握间谍 $2$ 的证据（$1$ 可以揭发 $2$）。
  • 间谍 $2$ 掌握间谍 $1$ 的证据（$2$ 可以揭发 $1$）。
• 由于间谍 $2$ 可以被收买，收买后他揭发间谍 $1$，从而控制间谍 $1$。因此可以控制所有间谍，最小费用为 $512$。

数据范围

• $1 \le n \le 3000$
• $1 \le p \le n$
• $1 \le r \le 8000$
• 每个收买的费用为非负数且不超过 $20000$

时空限制

• 时间限制：1000 ms
• 内存限制：562144 KB

注意：本题需要先通过强连通分量缩点（Tarjan 算法），然后对于每个强连通分量，如果分量内有可以被收买的间谍，则收买该分量的最小费用是其中可收买间谍的最小费用；如果分量内没有可收买的间谍，则该分量必须通过其他分量揭发控制（即分量入度不为 $0$）。如果存在一个强连通分量既没有可收买的间谍，也没有入度（即其他分量无法揭发它），则无法控制该分量中的间谍，输出编号最小的间谍编号。如果所有分量都可以被控制，则收买所有入度为 $0$ 且内部有可收买间谍的分量（费用取最小），注意对于入度为 $0$ 但内部没有可收买间谍的分量，必须通过其他分量控制（所以这种情况会导致无法控制）。因此算法步骤：

1. 求强连通分量。
2. 处理每个分量内的可收买最小费用，以及分量内最小的间谍编号。
3. 缩点后计算每个分量的入度。
4. 检查是否存在入度为 $0$ 且内部没有可收买间谍的分量，如果存在则无法控制，输出该分量中最小的间谍编号。
5. 否则可以控制，答案为所有入度为 $0$ 的分量的最小收买费用之和。