题目描述

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

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

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

输入输出格式

输入格式：

第一行只有一个整数\(n\)。

第二行是整数\(p\)。表示愿意被收买的人数，\(1≤p≤n\)。

接下来的\(p\)行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过\(20000\)。

紧跟着一行只有一个整数\(r\)，\(1≤r≤8000\)。然后\(r\)行，每行两个正整数，表示数对\((A, B)\)，\(A\)间谍掌握\(B\)间谍的证据。

输出格式：

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

输入输出样例

输入样例#1：

3
2
1 10
2 100
2
1 3
2 3

输出样例#1：

YES
110

输入样例#2：

4
2
1 100
4 200
2
1 2
3 4

输出样例#2：

NO
3

思路：

可以看出此题有两种情况:

一是有的罪犯既不能贿赂他也没有罪犯能揭发他，那么此题无解，我们在遍历时打上标记，然后从小到大枚举，只要遇见没有标记的就输出然后退出即可。

二是所有的罪犯都能直接或间接地被能贿赂的罪犯揭发。很明显，也有两种情况，一是没有环，那么资金就是贿赂那个没有入度的罪犯，二是有环，那么资金就是那个环里罪犯所需资金最小的。我们想，如果我们把环里的罪犯缩成一个点，那么全都是前者的情况了。然后就可以\(tarjan\)缩点做了。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<stack>
#define maxn 3007
using namespace std;
int num,n,m,vis[maxn],cnt,js,head[maxn],dfn[maxn],low[maxn];
int bel[maxn],block[maxn],w[maxn],p,rd[maxn],zrj;
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int v,nxt;
}e[8007];
const int inf=0x3f3f3f3f;
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
stack<int>q;
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x=-1;js++;
    while(x!=u) {
      x=q.top();q.pop();
      bel[x]=js;
      block[js]=min(block[js],w[x]);
      vis[x]=0;
    }
  }
}
int main() {
  n=qread(),p=qread();
  memset(block,0x3f,sizeof(block));
  memset(w,0x3f,sizeof(w));
  for(int i=1,x,y;i<=p;++i) {
    x=qread(),y=qread();
    w[x]=y;
  }
  m=qread();
  for(int i=1,u,v;i<=m;++i) {
    u=qread(),v=qread();
    ct(u,v);
  }
  for(int i=1;i<=n;++i) if(!dfn[i]&&w[i]!=inf) tarjan(i);
  for(int i=1;i<=n;++i) {
    if(!dfn[i]) {
      printf("NO\n%d\n",i);
      return 0;
    }
  }
  for(int u=1;u<=n;++u) {
    for(int i=head[u];i;i=e[i].nxt) {
      int v=e[i].v;
      if(bel[u]!=bel[v]) rd[bel[v]]++;
    }
  }
  for(int i=1;i<=js;++i) if(!rd[i]) zrj+=block[i];
  printf("YES\n%d\n",zrj);
  return 0;
}