The
country is overwhelmed by agents from foreign secret services. Not only do they steel
secret information, but also spy on each other.
We say that an agent A
unmasked an agent B, if A collected sufficient documents to arrest an agent
B. Some agents take bribes - for the certain amount of money they are
ready to hand over all the documents they have. So when we buy certain agents, we may initiate a chain of
arrests (if we arrest an agent we take
all his documents) which will lead to a liquidation of all the agents in the country.
Our
home counterintelligence provided us with the number of foreign agents in the
country, the information who and at what price may be corrupted, as well as what
agents unmasked whom. The number of agents is
equal to n <= 3000; and they have numbers from 1 to n.
Task
Write a program which:
reads from the text file AGE.IN information provided by
counterintelligence,
verifies, whether it is possible to initiate a chain of
arrests that will lead to a liquidation of all the agents in the country
by corrupting some of the agents, and if its possible computes the minimal
cost of such corrupting, otherwise finds a number of any agent that cannot
be arrested or corrupted,
writes the result into the text file AGE.OUT.
Input
In the first line of the text file AGE.IN there is written one integer n.
This is the number of all the agents operating in the country, 1<= n
<= 3000.
In the second line there is written one integer p. This is the number of
agents who take bribes, 1<= p <= n.
In each of the following n lines there are written two integers. The first is the number of
an agent and the second is the smallest amount of
money he would accept as a bribe - it is not grater then 20000.
The next line contains one integer r, 1 <= r <= 8000. This is the
number of pairs (A,B), such that the agent A unmasked
the agent B.
In the following r lines there are written all these pairs. In each of
these lines there are written two different positive integers from the set
{1, 2, ... ,n} separated by a single space. The first of them is the
number of an agent who unmasked another agent, and the second one is the
number of an agent that was unmasked.
Output
In the first line of the text file AGE.OUT there should be written one
word: "TAK" ('yes' in Polish) - if it is possible to arrest all
the agents operating in the country; or "NIE" ('no' in Polish) -
if otherwise.
The second line should contain one positive integer: the minimal cost of
corrupting agents whose documents may initiate a chain of arrests
that will lead to a liquidation of all the agents in the country, or the
number of any agent that cannot be arrested or corrupted.
Example
For the input file AGE.IN:
3
2
1 10
2 100
2
1 3
2 3
your program should produce the output file AGE.OUT:
TAK
110
For the input file AGE.IN:
4
2
1 100
4 200
2
1 2
3 4
your program should produce the output file AGE.OUT:
NIE
3
Your program should look for the file AGE.IN in the current directory and
produce the output file AGE.OUT in the current directory too. The file containing
the source code of your program should have a name AGE.???, whereas you should put
three-letter abbreviation of the used programming language name instead of ???. The
same program in executable form should be written in the file AGE.EXE