지구 종말
시간 제한7초메모리 제한1024 MB
우주 왕복선이 생존자를 한 명씩 지구에서 화성으로 옮길 때, 금지된 세 명 조합이 같은 행성에 모이지 않으면서 모두 탈출할 수 있는지 판정한다.
문제
윤창기는 서울대학교 화학부 종신교수이다.
오늘 윤창기 교수는 문제 지문에 쓸 만한 컨텐츠를 만들기 위해 지구를 파괴했다.
살아남은 명의 생존자들은 화성으로 탈출하기 위해 우주 정거장에 모였다. 각 생존자는 이상 이하의 서로 다른 정수 번호로 구분된다.
우주 정거장에는 화성과 지구를 오가는 우주 왕복선이 있다. 왕복선은 윤창기 교수만이 조종할 수 있으며, 조종사 외에 추가로 한 명이 더 탈 수 있다.
윤창기 교수는 길이 의 리스트를 가지고 있다. 이 리스트에는 각각 3명의 서로 다른 생존자가 적혀 있다. 윤창기 교수가 행성을 비운 사이, 이 리스트에 적혀 있는 세 생존자가 하나의 행성에 모이게 된다면, 이들은 정치 얘기를 하다가 핵 전쟁을 일으킬 것이고, 지구와 화성은 그 즉시 폭파될 것이다.
과연 모든 생존자가 무사히 화성으로 탈출할 수 있을까?
입력
이 문제는 여러 개의 테스트 케이스가 주어진다. 첫 번째 줄에 테스트 케이스의 개수 가 주어지고, 이후 줄에 걸쳐 다음과 같은 정보가 주어진다.
첫 번째 줄에 두 정수 이 주어진다.
이후 개의 줄에 서로 다른 생존자 셋의 번호 가 주어진다.
출력
각 테스트 케이스에 대해, 모든 생존자가 탈출할 수 있으면 TAK, 아니면 NIE를 한 줄로 출력한다.
제한
- 의 합은 이하이다.
- 의 합은 이하이다.