시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB0000.000%

문제

Przewidywanie ruchów przeciwnika to bezcenna umiejętność w rywalizacji każdego rodzaju. Kluczowym elementem jest możliwość odpowiedniej reakcji na ruch przeciwnika. Każdy ruch stawia nas jednak w innej sytuacji i zmienia możliwości dalszych ruchów.

Przyjmijmy, że analizujemy rywalizację, w której można znaleźć się w jednej z n sytuacji. Załóżmy ponadto, że w każdej z nich rozważamy dostępność dwóch typów ruchów oznaczonych jako A i B. Atakujący pierwszy wchodzi do rozgrywki i wybiera swoją sytuację początkową, w której się znajduje. Następnie Broniący również wybiera sytuację początkową różną od sytuacji początkowej Atakującego. Potem następuje faza rywalizacji. Atakujący musi wykonać ruch typu A lub B, o ile jest on dostępny w sytuacji w której się znajduje. Gdy nie może wykonać ruchu to przegrywa. Broniący musi odpowiedzieć ruchem tego samego typu ze swojej sytuacji. Jeśli nie jest to możliwe — przegrywa.

Twoim zadaniem jest napisanie programu, który analizuje sytuacje i ruchy w nich dostępne i powie, czy Broniący może zawsze odpowiadać na ruchy przeciwnika.

입력

Pierwsza linia wejścia zawiera małą liczbę całkowitą z – liczbę zestawów danych występujących kolejno po sobie. Opis jednego zestawu jest następujący:

W pierwszej linii występuje liczba całkowita n określająca liczbę sytuacji (2 ≤ n ≤ 2000). W kolejnych n liniach znajdują się opisy ruchów możliwych do wykonania w każdej sytuacji. Każda linia zawiera dwie liczby całkowite a, b (0 ≤ a, b ≤ n) opisujące odpowiednio sytuacje do których przejdziemy wybierając ruch typu A lub B. Liczba 0 oznacza brak możliwości wykonania ruchu danego typu.

출력

Dla każdego zestawu danych wypisz słowo TAK jeśli Broniący może zawsze odpowiadać na ruchy Atakującego. Gdy nie jest to możliwe wypisz NIE.

예제 입력 1

2
4
2 0
1 0
0 4
0 3
3
2 3
0 1
1 0

예제 출력 1

TAK
NIE