Agents

The country is overrun by agents from foreign secret services. They do not only steal secret information, they also spy on one another. We say that an agent $A$ unmasked an agent $B$ if $A$ has collected enough documents to have $B$ arrested.

Some agents take bribes: for a certain amount of money they hand over every document they hold. So by buying off some agents we can start a chain of arrests (arresting an agent gives us all of that agent's documents), and this chain can lead to the liquidation of every agent in the country.

Counterintelligence has given us the number of foreign agents in the country, who can be bribed and at what price, and which agents unmasked which. There are $n$ agents ($n \le 3000$), numbered from $1$ to $n$.

Write a program that:

• reads the counterintelligence data from standard input,
• decides whether it is possible to bribe some agents so that the resulting chain of arrests liquidates every agent in the country, and if so computes the minimum total bribe cost; otherwise reports the number of an agent that can neither be arrested nor bribed,
• writes the result to standard output.

The first line contains one integer $n$, the number of agents operating in the country ($1 \le n \le 3000$).

The second line contains one integer $p$, the number of agents who take bribes ($1 \le p \le n$). Each of the next $p$ lines contains two integers: the number of an agent and the smallest bribe that agent will accept, which is at most $20000$.

The next line contains one integer $r$ ($1 \le r \le 8000$), the number of pairs $(A, B)$ such that agent $A$ unmasked agent $B$. Each of the following $r$ lines contains two different integers from $\{1, 2, \ldots, n\}$ separated by a single space: the agent who did the unmasking, followed by the agent who was unmasked.

On the first line print TAK (Polish for "yes") if it is possible to liquidate every agent in the country, or NIE (Polish for "no") otherwise.

• If it is possible, the second line must contain a single integer: the minimum total cost of bribing agents whose documents start a chain of arrests that liquidates every agent.
• If it is not possible, the second line must contain the number of an agent who can neither be arrested nor bribed. If several such agents exist, print the smallest number.