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