화려한 방어

상대의 움직임을 예측하는 능력은 모든 종류의 대결에서 매우 값지다. 핵심은 상대의 움직임에 적절히 응수할 수 있는가이며, 각 움직임은 우리를 서로 다른 상황에 놓이게 하고 이후에 할 수 있는 움직임의 가능성까지 바꾼다.

$n$개의 상황 중 하나에 놓일 수 있는 대결을 분석한다고 하자. 각 상황에서는 A와 B로 표시된 두 종류의 움직임을 할 수 있는지가 정해져 있다. 먼저 공격자가 대결에 들어와 자신의 시작 상황을 고른다. 그다음 방어자가 공격자와 다른 자신의 시작 상황을 고른다. 이후 대결이 진행된다.

• 공격자는 현재 상황에서 가능한 A 또는 B 타입의 움직임을 하나 골라 반드시 실행해야 한다. 어떤 움직임도 할 수 없으면 공격자가 패배한다.
• 방어자는 공격자가 고른 것과 같은 타입의 움직임을 자신의 상황에서 실행해 응수해야 한다. 그것이 불가능하면 방어자가 패배한다.

주어진 상황들과 각 상황에서 가능한 움직임을 분석하여, 방어자가 공격자의 움직임에 항상 응수할 수 있는지를 판별하는 프로그램을 작성하여라.

정확히 말하면, 공격자가 어떤 시작 상황을 고르더라도 방어자가 그와 다른 어떤 시작 상황을 골라, 이후 공격자가 어떻게 움직이든 매번 같은 타입으로 응수할 수 있을 때에만 "방어자가 항상 응수할 수 있다"고 한다.

첫 줄에는 연달아 주어지는 데이터 집합의 개수를 나타내는 작은 정수 $z$가 주어진다. 각 데이터 집합의 형식은 다음과 같다.

첫 줄에 상황의 개수를 나타내는 정수 $n$이 주어진다 ($2 \le n \le 2000$). 이어지는 $n$개의 줄에는 각 상황에서 할 수 있는 움직임이 적혀 있다. $i$번째 줄에는 두 정수 $a$, $b$ ($0 \le a, b \le n$)가 주어지며, 각각 $i$번 상황에서 A 타입과 B 타입 움직임을 골랐을 때 이동하게 되는 상황의 번호를 뜻한다. 값이 $0$이면 해당 타입의 움직임을 할 수 없음을 뜻한다.

각 데이터 집합에 대해, 방어자가 공격자의 움직임에 항상 응수할 수 있으면 TAK를, 그렇지 않으면 NIE를 한 줄에 출력한다.