记录编号	39369	评测结果	AAAAAAAAAAAA
题目名称	聪明的推销员	最终得分	100
用户昵称	IMSL77	是否通过	通过
代码语言	Pascal	运行时间	0.019 s
提交时间	2012-07-09 16:49:50	内存使用	0.36 MiB

program salenet;
type
  integer=longint;
const
  maxn=4000;
  maxm=10000;
  INF=100000000;
var
  n,m:integer;
  p,time,tot,sl:integer;
  ver:array[1..maxn] of integer;
  en,next:array[1..maxm] of integer;
  cost:array[1..maxn] of integer;
  dfn,low:array[1..maxn] of integer;
  stack:array[1..maxn] of integer;
  instack:array[1..maxn] of boolean;
  tick:array[1..maxn] of integer;
  min:array[1..maxn] of integer;
  din:array[1..maxn] of integer;

  procedure Fopen;
  begin
    assign(input,'salenet.in'); reset(input);
    assign(output,'salenet.out'); rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input); close(output);
  end;

  procedure SetGraph;
  var
    i:integer;
    u,v:integer;
  begin
    readln(n); readln(p);
    for i:=1 to n do cost[i]:=INF;
    for i:=1 to p do begin readln(u,v); cost[u]:=v; end;
    readln(m);
    for i:=1 to m do
    begin
      readln(u,v);
      en[i]:=v; next[i]:=ver[u]; ver[u]:=i;
    end;
  end;

  procedure Floodfill(u:integer);
  var
    k:integer;
  begin
    dfn[u]:=1;
    k:=ver[u];
    while k>0 do begin if dfn[en[k]]=0 then Floodfill(en[k]); k:=next[k]; end;
  end;

  function NoSolution:boolean;
  var
    i:integer;
  begin
    fillchar(dfn,sizeof(dfn),0);
    for i:=1 to n do if cost[i]<INF then Floodfill(i);
    for i:=1 to n do if dfn[i]=0 then
    begin
      writeln('NO'); writeln(i);
      exit(true);
    end;
    exit(false);
  end;

  procedure DFS(u:integer);
  var
    k,v:integer;
  begin
    inc(time); dfn[u]:=time; low[u]:=time;
    inc(sl); stack[sl]:=u; instack[u]:=true;
    k:=ver[u];
    while k>0 do
    begin
      v:=en[k];
      if dfn[v]=0 then
      begin
        DFS(v);
        if low[v]<low[u] then low[u]:=low[v];
      end else if instack[v] then
        if dfn[v]<low[u] then low[u]:=dfn[v];
      k:=next[k];
    end;
    if low[u]=dfn[u] then
    begin
      inc(tot);
      while stack[sl]<>u do
      begin
        tick[stack[sl]]:=tot; instack[stack[sl]]:=false; dec(sl);
      end;
      tick[u]:=tot; instack[u]:=false; dec(sl);
    end;
  end;

  procedure Tarjan;
  var
    i:integer;
  begin
    fillchar(dfn,sizeof(dfn),0);
    fillchar(low,sizeof(low),0);
    time:=0; tot:=0; sl:=0;
    for i:=1 to n do if dfn[i]=0 then DFS(i);
    while sl>0 do begin inc(tot); tick[stack[sl]]:=tot; dec(sl); end;
  end;

  procedure Solve;
  var
    i,j:integer;
    sum:integer;
  begin
    if NoSolution then exit;
    Tarjan;
    for i:=1 to tot do min[i]:=INF;
    for i:=1 to n do if cost[i]<min[tick[i]] then min[tick[i]]:=cost[i];
    fillchar(din,sizeof(din),0);
    for i:=1 to n do
    begin
      j:=ver[i];
      while j>0 do
      begin
        if tick[i]<>tick[en[j]] then inc(din[tick[en[j]]]);
        j:=next[j];
      end;
    end;
    sum:=0;
    for i:=1 to tot do if din[i]=0 then inc(sum,min[i]);
    writeln('YES'); writeln(sum);
  end;

begin
  Fopen;
  SetGraph;
  Solve;
  Fclose;
end.