Experiment

Junwon works as a data scientist at Sunlin Internet Corporation. He wants to select beta testers for the company's new service.

There are $N$ users who are candidates for beta testers. Based on their past service usage records, the $N$ users are divided into $M$ user groups in total, and each user belongs to between $0$ and $M$ user groups. ($M = 0$ is possible. In this case, think of it as having no groups at all.)

When Junwon selects some of these $N$ users as beta testers, the following conditions must be satisfied.

• Condition 1: At most one beta tester can be selected from each user group.
• Condition 2: For any two users with opposing tendencies, at least one of them must be selected as a beta tester.
  • The pairs of users with opposing tendencies are given in the input.

Help Junwon select the beta testers.

The first line of the input gives four integers $N$, $M$, $A$, $B$.

The next $A$ lines each give two integers $i$, $j$. This means user $i$ belongs to group $j$, and satisfies $1 \le i \le N$, $1 \le j \le M$.

The next $B$ lines each give two integers $i$, $j$. This means user $i$ and user $j$ have opposing tendencies, and satisfies $1 \le i, j \le N$, $i \neq j$.

If Junwon can select the beta testers so that the conditions are satisfied, print "TAK"; otherwise, print "NIE".

• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• $0 \le A \le 5 \times 10^5$
• $0 \le B \le 2 \times 10^5$