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

• 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