나누어떨어짐

Hektor는 Wiktor에게 늘 온갖 종류의 수수께끼를 낸다. 오늘 Wiktor를 기다리는 문제는 유난히 어렵다. Hektor가 완전히 새로운 종류의 퍼즐을 만들어 냈기 때문이다.

Hektor는 서로 다른, 0이 아닌 자연수 $N$개를 종이에 적고 각각을 원으로 둘러쌌다. 그런 다음 $a$가 $b$의 약수인(즉 $b$가 $a$로 나누어떨어지는) 모든 순서쌍 $(a, b)$에 대해 $a$에서 $b$로 향하는 화살표를 그렸다. 마지막으로 원 안에 적어 둔 수를 모두 지웠다.

퍼즐은 다음과 같다. 서로 다른, 0이 아닌 자연수 $N$개를 각 원에 배정하여 Hektor가 그린 화살표와 정확히 일치하게 만들 수 있는지 판별하는 것이다. 즉, 화살표로 이어진 순서쌍(그리고 오직 그 순서쌍들)에서만 화살표 시작 원의 수가 끝 원의 수의 약수가 되어야 한다.

그런 배정이 존재하는 경우, 모든 수를 $100$자리 이하로 잡을 수 있음이 보장된다.

첫 줄에 테스트 세트의 개수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 세트가 차례로 주어진다.

각 세트의 첫 줄에는 채워야 할 원의 개수 $N$과 화살표의 개수 $M$ ($1 \le N \le 50$, $0 \le M$)이 주어진다. 이어지는 $M$개의 줄에는 화살표가 한 개씩 주어지는데, 각 줄에는 공백으로 구분된 서로 다른 두 자연수 $a$와 $b$ ($1 \le a, b \le N$, $a \ne b$)가 있고 이는 $a$번 원에서 $b$번 원으로 향하는 화살표를 뜻한다. 같은 화살표가 중복해서 주어지지는 않는다.

각 세트마다, 조건을 만족하도록 원에 수를 배정하는 방법이 존재하면 TAK을, 존재하지 않으면 NIE를 한 줄에 출력한다.