记录编号	307595	评测结果	AAAAAAAAAAAAA
题目名称	间谍网络	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2016-09-15 16:04:31	内存使用	0.33 MiB

#include <stdio.h>
#include <string.h>

template <typename T> inline void Read(T &num) {
	num = 0; char ch; short minus = 1;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') ch = getchar(), minus = -1;
	while (num = num * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	num *= minus;
}

const size_t maxn = 3000 + 10, maxm = 8000 + 10;

int mon[maxn];

class Graph {
	struct Edge { int v, ne; } E[maxm];
	int pre[maxn], tot;
	
	int dfs_time, dfn[maxn], low[maxn];
	int Stack[maxn], tail;
	bool insta[maxn];
	
	inline void SCC_Tarjan(int u) {
		dfn[u] = low[u] = ++dfs_time;
		Stack[++tail] = u; insta[u] = true;
		int v;
		for (int i = pre[u]; i; i = E[i].ne) {
			v = E[i].v;
			if (!dfn[v]) {
				SCC_Tarjan(v);
				if (low[v] < low[u]) low[u] = low[v];
			}
			else if (insta[v] && dfn[v] < low[u]) low[u] = dfn[v];
		}
		if (dfn[u] == low[u]) {
			++cnt;
			do {
				v = Stack[tail--];
				insta[v] = false;
				scc[v] = cnt;
				if (mon[v] < val[cnt]) val[cnt] = mon[v];
				if (v < sccno[cnt]) sccno[cnt] = v;
			} while (v != u);
		}
	}
	
public:
	int n, m;
	int val[maxn];
	int scc[maxn], cnt, sccno[maxn];
	bool in0[maxn];
	
	#define clr(a, b) memset(a, b, sizeof(a))
	inline Graph() {
		tot = cnt = dfs_time = tail = 0;
		clr(pre, 0);
		clr(val, 127);
		clr(sccno, 127);
		clr(in0, true);
		clr(dfn, 0);
		clr(low, 0);
		clr(scc, 0);
		clr(insta, 0);
	}
	#undef clr
	
	inline void Insert(const int &u, const int &v) {
		E[++tot].v = v; E[tot].ne = pre[u]; pre[u] = tot;
	}
	
	inline void get_SCC() {
		for (int i = 1; i <= n; ++i) if (!dfn[i]) SCC_Tarjan(i);
	}

	inline void solve(bool &fail, int &ans) {
		for (int u = 1; u <= n; ++u)
			for (int i = pre[u]; i; i = E[i].ne)
				if (scc[u] != scc[E[i].v]) in0[scc[E[i].v]] = false;
		int minn = 0x7fffffff, totv = 0;
		for (int i = 1; i <= cnt; ++i) if (in0[i]) {
			if (0x7f7f7f7f == val[i]) {
				fail = true;
				if (sccno[i] < minn) minn = sccno[i];
			}
			else totv += val[i];
		}
		if (!fail) ans = totv;
		else ans = minn;
	}
};

#define SUBMIT

int main() {
#ifdef SUBMIT
	freopen("spyweb.in", "r", stdin);
	freopen("spyweb.out", "w", stdout);
#endif

	Graph G;
	memset(mon, 127, sizeof(mon));
	int nl; Read(G.n); Read(nl);
	int a, b;
	for (int i = 1; i <= nl; ++i) {
		Read(a); Read(b);
		mon[a] = b;
	}
	Read(G.m);
	for (int i = 1; i <= G.m; ++i) {
		Read(a); Read(b);
		G.Insert(a, b);
	}
	G.get_SCC();
	bool fail = false;
	int ans;
	G.solve(fail, ans);
	if (!fail) printf("YES\n");
	else printf("NO\n");
	printf("%d\n", ans);
	
#ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif	
	return 0;
}