#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int N = 3010;
const int M = 8010;
int n,m,p;
int w[N];
int h[N],e[M],ne[M],idx;
int scc_cnt;
int id[N];
int dfn[N],low[N];
int timestamp;
bool st[N];
int Size[N];
stack<int> q;
int rout[N];
queue<int> Scc[N];
void add(int a,int b) {
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
q.push(u);
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(!dfn[j]) {
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(st[i]) low[u] = min(low[u],low[j]);
}
if(dfn[u] == low[u]) {
scc_cnt ++;
int y = 0;
do {
y = q.top();
q.pop();
id[y] = scc_cnt;
Size[scc_cnt] ++;
st[y] = 0;
Scc[scc_cnt].push(y);
} while(y != u);
}
}
int main() {
memset(h,-1,sizeof h);
cin >> n;
cin >> p;
for(int i = 1; i <= p; i ++) {
int ind,val;
cin >> ind >> val;
w[ind] = val;
}
cin >> m;
for(int i = 1; i <= m; i ++) {
int a,b;
cin >> a >> b;
add(a,b);
}
for(int i = 1; i <= n; i ++) {
if(!dfn[i]) tarjan(i);
}
for(int i = 1; i <= n; i ++) {
for(int j = h[i]; ~j; j = ne[j]) {
int b = id[e[j]],a = id[i];
if(a != b) rout[b] ++;
}
}
int res = 0,min_idx = 0x3f3f3f3f;
bool flg = 0;
for(int i = 1; i <= scc_cnt; i ++) {
if(rout[i] == 0) {
bool f = 0;
int minn = 0x3f3f3f3f;
int Min = 0x3f3f3f3f;
while(!Scc[i].empty()) {
int t = Scc[i].front();
Scc[i].pop();
Min = min(Min,t);
if(w[t]) {
minn = min(minn,w[t]);
f = 1;
}
}
if(f) res += minn;
else {
flg = 1;
min_idx = min(min_idx,Min);
}
}
}
if(flg) {
cout << "NO" << endl << min_idx;
} else {
cout << "YES" << endl << res;
}
}
tarjan 缩点,实在调不出来了,萌新求助