19703번 - 실험

문제

선린인터넷주식회사에서 데이터 사이언티스트로 일하는 준원이는 회사의 새로운 서비스의 베타 테스터를 선정하고자 한다.

베타 테스터의 후보가 되는 유저로는 총 $N$명의 유저가 있다. $N$명의 유저들은 그간의 서비스 사용 기록을 기반으로 총 $M$개의 유저 그룹으로 나누어지는데, 각 유저는 0ドル$개 이상 $M$개 이하의 유저 그룹에 속한다. ($M = 0$일 수도 있다. 이 경우, 아무 그룹도 없다고 생각하면 된다.)

준원이가 이들 $N$명의 유저 가운데 몇 명의 베타 테스터를 뽑을 때 다음 조건을 반드시 만족해야 한다.

• 조건 1: 하나의 유저 그룹에서는 최대 한 명의 베타 테스터만 뽑을 수 있다.
• 조건 2: 서로 반대되는 성향의 두 유저 가운데 최소 한 명은 베타 테스터로 뽑아야 한다.
  • 서로 반대되는 성향을 가지는 유저의 쌍들은 입력을 통해 주어진다.

준원이를 도와 베타 테스터들을 선정해주자.

입력

입력의 첫 줄에는 네 정수 $N,ドル $M,ドル $A,ドル $B$가 주어진다.

이후 $A$개의 줄에 걸쳐 두 정수 $i,ドル $j$가 주어진다. 이는 유저 $i$가 그룹 $j$에 속함을 의미하며, 1ドル \le i \le N,ドル 1ドル \le j \le M$을 만족한다.

이후 $B$개의 줄에 걸쳐 두 정수 $i,ドル $j$가 주어진다. 이는 유저 $i$와 유저 $j$의 성향이 반대됨을 의미하며, 1ドル \le i, j \le N,ドル $i \neq j$를 만족한다.

출력

조건들을 만족하게 준원이가 베타 테스터를 선정할 수 있으면 TAK, 아니면 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$

힌트