Description

由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果

我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

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

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

Input

第一行只有一个整数n。

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

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

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

Output

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

Sample Input 1

2
1
2 512
2
1 2
2 1

Sample Output 1

YES
512

题目大意：

强连通分量+Tar缩点，只要找出每个强连通分量中价值最小的点即可，最后找入度为0的点即可，入度为0就说明必须收买。

#include<bits/stdc++.h>

using namespace std;
const int maxn = 3e3+5;
const int inf = 0x3f3f3f3f;
int low[maxn],dfn[maxn],Stack[maxn];
int in[maxn],val[maxn],t[maxn],minval[maxn];
bool instack[maxn],vis[maxn];
int tot,cnt,num,n,p,r;
vector<int>e[maxn];


void Tar(int u)
{
    low[u] = dfn[u] = ++tot;
    Stack[++num] = u;
    instack[u] = true;
    for(int i = 0 ; i < e[u].size() ; i++)
    {
        int v = e[u][i];
        if(!dfn[v])
        {
            Tar(v);
            low[u] = min(low[u],low[v]);        
        }
        else if(instack[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        while(u != Stack[num])
        {
            minval[cnt] = min(minval[cnt],val[Stack[num]]);
            t[Stack[num]] = cnt;
            instack[Stack[num]] = false;
            num--;
        }
        minval[cnt] = min(minval[cnt],val[Stack[num]]);
        t[Stack[num]] = cnt;
        instack[Stack[num]] = false;
        num--;
        cnt++;
    }
} 

int main()
{
    fill(minval,minval+maxn,inf);
    cin >> n >> p;
    for(int i = 0 ; i < p ; i++)
    {
        int u,w;
        cin >> u >> w;
        val[u] = w;
        vis[u] = true;
    }
    cin >> r;
    for(int i = 0 ; i < r ; i++)
    {
        int u,v;
        cin >> u >> v;
        if(vis[u])
        {
            e[u].push_back(v);    
        }
        vis[v] = true;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(vis[i] == false)
        {
            cout << "NO\n" << i << endl;
            return 0;
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(!dfn[i])
            Tar(i);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < e[i].size() ; j++)
        {
            int u = i,v = e[u][j];
            if(t[u] != t[v])
            {
                in[t[v]]++;
            }
        }
    }
    int ans = 0;
    for(int i = 0 ; i < cnt ; i++)
    {
        if(!in[i] && minval[i] != inf)
            ans += minval[i];
    }
    cout << "YES\n" << ans << endl;
    return 0;
}