20656번 - 지구 종말

윤창기는 서울대학교 화학부 종신교수이다.

오늘 윤창기 교수는 문제 지문에 쓸 만한 컨텐츠를 만들기 위해 지구를 파괴했다.

살아남은 $N$ 명의 생존자들은 화성으로 탈출하기 위해 우주 정거장에 모였다. 각 생존자는 $1$ 이상 $N$ 이하의 서로 다른 정수 번호로 구분된다.

우주 정거장에는 화성과 지구를 오가는 우주 왕복선이 있다. 왕복선은 윤창기 교수만이 조종할 수 있으며, 조종사 외에 추가로 한 명이 더 탈 수 있다. 

윤창기 교수는 길이 $M$ 의 리스트를 가지고 있다. 이 리스트에는 각각 3명의 서로 다른 생존자가 적혀 있다. 윤창기 교수가 행성을 비운 사이, 이 리스트에 적혀 있는 세 생존자가 하나의 행성에 모이게 된다면, 이들은 정치 얘기를 하다가 핵 전쟁을 일으킬 것이고, 지구와 화성은 그 즉시 폭파될 것이다.

과연 모든 생존자가 무사히 화성으로 탈출할 수 있을까?

이 문제는 여러 개의 테스트 케이스가 주어진다. 첫 번째 줄에 테스트 케이스의 개수 $T$ 가 주어지고, 이후 $T$ 줄에 걸쳐 다음과 같은 정보가 주어진다. 

첫 번째 줄에 두 정수 $N, M$ 이 주어진다.

이후 $M$ 개의 줄에 서로 다른 생존자 셋의 번호 $a, b, c$ 가 주어진다.

각 테스트 케이스에 대해, 모든 생존자가 탈출할 수 있으면 TAK, 아니면 NIE를 한 줄로 출력한다.

• $1 \le T \le 257$
• $1 \le N \le 10\,000$
• $0 \le M \le 25\,000$
• $1 \le a < b < c \le N$
• $N$ 의 합은 $334518$ 이하이다.
• $M$ 의 합은 $650915$ 이하이다.