시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 87 | 25 | 10 | 27.027% |
선린인터넷주식회사에서 데이터 사이언티스트로 일하는 준원이는 회사의 새로운 서비스의 베타 테스터를 선정하고자 한다.
베타 테스터의 후보가 되는 유저로는 총 $N$명의 유저가 있다. $N$명의 유저들은 그간의 서비스 사용 기록을 기반으로 총 $M$개의 유저 그룹으로 나누어지는데, 각 유저는 $0$개 이상 $M$개 이하의 유저 그룹에 속한다. ($M = 0$일 수도 있다. 이 경우, 아무 그룹도 없다고 생각하면 된다.)
준원이가 이들 $N$명의 유저 가운데 몇 명의 베타 테스터를 뽑을 때 다음 조건을 반드시 만족해야 한다.
준원이를 도와 베타 테스터들을 선정해주자.
입력의 첫 줄에는 네 정수 $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
를 출력하라.
2 3 0 0
TAK
5 1 5 10 1 1 2 1 3 1 4 1 5 1 2 1 3 1 2 3 1 4 4 2 4 3 1 5 2 5 3 5 5 4
NIE