In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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 unmasked an agent , if collected sufficient documents to arrest an agent .
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 ; and they have numbers from to .
Write a program which:
In the first line of the standard input there is written one integer . This is the number of all the agents operating in the country, . In the second line there is written one integer . This is the number of agents who take bribes, . In each of the following 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 .
The next line contains one integer , . This is the number of pairs , such that the agent unmasked the agent . In the following lines there are written all these pairs. In each of these lines there are written two different positive integers from the set 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.
In the first line of the standard output there should be written one word: TAK (which means “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.
For the input data:
3 2 1 10 2 100 2 1 3 2 3
the correct result is:
whereas for the input data:
4 2 1 100 4 200 2 1 2 3 4
the correct output is:
Task author: Marcin Kubica.