Chochlik

19세기의 어느 공장에서는 전동 벨트로 동력을 전달했다. 공장은 아주 잘 돌아가고 있었는데, 어느 날 장난꾸러기 요정이 몰래 들어와 일부 벨트의 연결을 뒤바꿔 놓았다. 공장 주인은 지금처럼 벨트가 연결된 상태에서도 공장이 제대로 돌아갈 수 있을지 궁금해한다.

서로 다른 두 바퀴를 잇는 방법은 두 가지다. 어떤 바퀴가 한 방향으로 돌 때, $A$ 방식으로 연결된 바퀴는 같은 방향으로 돌고, $B$ 방식으로 연결된 바퀴는 반대 방향으로 돈다.

바퀴를 전동 벨트로 잇는 두 가지 방법.

어떤 한 바퀴를 돌리기 시작했을 때 다른 어떤 바퀴도 서로 반대인 두 방향으로 동시에 돌도록 강요받지 않는다면, 그 부서는 제대로 작동할 수 있다.

각 부서에 대해, 지금 연결된 벨트 상태로 그 부서가 제대로 작동할 수 있는지 판정하는 프로그램을 작성하여라.

첫째 줄에 공장의 부서 개수를 나타내는 정수 $d$ ($1 \le d \le 10$)가 주어진다.

이어서 각 부서의 정보가 주어진다. 각 부서 정보의 첫째 줄에는 두 정수 $k$와 $p$ ($1 \le k \le 100\,000$, $0 \le p \le 100\,000$)가 주어지며, 각각 그 부서의 바퀴 개수와 바퀴 사이의 연결 개수를 뜻한다. 다음 $p$개의 줄에는 각각 공백으로 구분된 두 정수 $a_i$, $b_i$와 한 글자 $c_i$가 주어진다 ($1 \le a_i, b_i \le k$, $c_i \in \{A, B\}$, $a_i \ne b_i$). 이는 연결된 두 바퀴의 번호와 둘 사이의 연결 방식을 나타낸다.

두 바퀴가 둘 이상의 벨트로 연결되어 있을 수도 있다.

정확히 $d$개의 줄을 출력한다. $i$번째 줄에는 다음 한 단어를 출력한다.

• $i$번째 부서가 제대로 작동할 수 있으면 TAK
• 그렇지 않으면 NIE

예시 설명. 첫 번째 부서는 제대로 작동할 수 없다. $1$번 바퀴를 오른쪽으로 돌리면 $2$번 바퀴가 오른쪽과 왼쪽으로 동시에 돌아야 하는데, 이런 움직임은 불가능하기 때문이다. 두 번째 부서에는 벨트가 하나도 없으므로 올바른 구성이다.