提示: 欢迎访问OurACM平台。
Problem 1719 Spy Network

Accept: 94    Submit: 308
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Due to the large number of infiltration of foreign espionage, national security is at a high level of crisis. If Spy A grasps Spy B’s evidence of crimes, Spy A can exposed Spy B. Some spies take bribes, and if we give a number of dollars to them, they are willing to hand over all their evidences they have. Therefore, if we are able to buy some spies, we would control the whole spy network.
That is because once we arrest a spy, we will get all evidences he has. Then we can arrest new spies to acquire new information.
Now we know those who are willing to take dollars, and the number of dollars they need. We know what evidences have been got for each spy as well. Suppose that there are n (n <= 3000) spies in total, who are labeled as a number between 1 and n.If we can control all spies, output minimal dollars required, otherwise output each spies we cannot control.

Input

The input consists of several test cases.For each case,the first line of input is an integer n. The second line is an integer p (1<=p<=n), which is the number of spies who accept dollars.Then following p lines, each of them contains two integers indicating the label of spies and the number he needs. An integer r (1 <= r <= 8000) followed, then r lines. Each contains two integers A and B, which means that Spy A has the evidence of Spy B.

Output

For each case, If we can control all spies, output “YES” in the first line and the minimal number of dollar we need in the second line. If we cannot, output “NO” in the first line and the label of spy that we cannot control and have the minimal number of label.

Sample Input

3 2 1 10 2 100 2 1 3 2 3 4 2 1 100 4 200 2 1 2 3 4

Sample Output

YES 110 NO 3

Source

FZU 2009 Summer Training Qualification -- Hero Revival 1

Submit  Back  Status  Discuss