3비트 컴퓨터의 역습

3비트 컴퓨터(KTB)가 엄청난 실패로 끝난 뒤, 바이트랜드의 과학자들은 새로운 멋진 아이디어를 떠올렸습니다. 바로 양자 3비트 컴퓨터(KKTB)입니다. 이제 KTB는 진짜 도전인 KKTB를 위한 준비운동 정도로 여겨집니다.

새 양자 컴퓨터는 지금까지 없던 엄청난 성능을 가질 것으로 예상됩니다. 어쩌고저쩌고, 올림피아드용 골치 아픈 문제도 잔뜩 나올 것이고, 어쩌고저쩌고. 본론으로 들어갑시다.

예전과 마찬가지로 가장 근본적인 어려움은 메모리 초기화입니다. 다만 양자 컴퓨터에서는 문제의 성격이 완전히 다릅니다. KKTB의 각 소자에 가하는 모든 연산은 부작용을 일으켜 컴퓨터의 다른 소자에도 영향을 줍니다. 이 부작용을 상쇄하는 비용이 매우 크기 때문에, 비트를 하나씩 초기화하는 방식은 불가능합니다. 대신 다른 접근법이 있는데, 바로 중거리 제어 펄스(SISZ)입니다. 과학자들은 각 메모리 비트에 미치는 영향을 정확히 계산할 수 있는 펄스를 만들 수 있습니다. 이 펄스는 매우 빠르게 방출할 수 있어서, 펄스를 많이 사용하더라도 비트를 하나씩 초기화하는 것보다 비용이 적게 듭니다. 그렇다면 SISZ만으로 메모리 전체를 0으로 만들 수 있을까요? 이 질문에 답하는 프로그램을 작성하는 것이 여러분의 과제입니다.

좀 더 형식적으로 말하면, 각 메모리 비트는 $0, \dots, n-1$로 번호가 매겨진 $n$개의 상태 중 하나에 있을 수 있습니다. SISZ 펄스는 모든 비트에 동일한 방식으로 작용하므로, 함수 $f : \{0, \dots, n-1\} \to \{0, \dots, n-1\}$로 볼 수 있습니다. 예를 들어 $f(3) = 5$는 펄스 $f$를 방출한 뒤 상태 $3$에 있던 모든 비트가 상태 $5$로 바뀐다는 뜻입니다. 과학자들은 펄스 $f_1, \dots, f_k$를 방출할 수 있습니다. 초기 상태와 무관하게 모든 비트를 상태 $0$으로 만드는(0으로 초기화하는) 펄스의 순서가 존재하는지 판정하는 것이 과제입니다.

과제

다음을 수행하는 프로그램을 작성하세요.

• 사용할 수 있는 펄스들의 정보를 입력받고,
• 메모리를 0으로 만들 수 있는지 판정하여,
• 그 답을 표준 출력에 씁니다.

각 테스트는 여러 개의 데이터 묶음으로 이루어집니다. 표준 입력의 첫 줄에는 데이터 묶음의 개수를 나타내는 자연수 $T$ ($1 \le T \le 10$)가 주어집니다. 그다음에 데이터 묶음들이 이어집니다.

하나의 데이터 묶음은 두 자연수 $n$, $k$ ($1 \le n \le 200$, $1 \le k \le 5$)가 적힌 줄로 시작합니다. 여기서 $n$은 비트가 가질 수 있는 서로 다른 상태의 개수이고, $k$는 사용할 수 있는 펄스의 개수입니다. 이어지는 $k$개의 줄에는 각 펄스의 정보가 있으며, $i$번째 줄은 $i$번째 펄스를 나타냅니다. 펄스 $f$의 정보는 정수 수열 $f(0)\ \dots\ f(n-1)$로, 각 메모리 비트의 상태에 $f$가 어떤 영향을 주는지를 나타냅니다. 이 수들은 공백 하나로 구분됩니다.

표준 출력에 데이터 묶음마다 한 줄씩, 총 $T$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 테스트에서 메모리를 0으로 만들 수 있으면 TAK(가능)을, 그렇지 않으면 NIE(불가능)를 출력합니다.