Kapitan Mambeks i domino

Ulubionym zajęciem Kapitana Mambeksa jest układanie domina składającego się z N różnych klocków. Każdy klocek domina składa się z dwóch połówek, na każdej z nich znajduje się liczba z zakresu 1, ..., 5 000. Klocki domina układa się w łańcuch, przy czym klocki można dołączać wyłącznie na jeden z dwóch końców łańcucha. Dołączyć można klocek który pasuje jedną połówką do połówki klocka znajdującego się na końcu łańcucha. Do danej połówki może być dołączony tylko jeden klocek. Domino uważa się za ułożone jeżeli wszystkie klocki można ułożyć w łańcuch oraz dopasowane są połówki klocków znajdujących się na obydwu końcach łańcucha.

Przykładowo, zestaw domina składający się z klocków [1 , 2] [1 , 3] [2 , 4] [3 , 4] można ułożyć w następujący sposób:

Niestety nie zawsze istnieje możliwość ułożenia domina. Przykładowo nie ma możliwości ułożenia zestawu domina składającego się z klocków [1 , 2] [2 , 3] [3 , 4] [4, 5], ponieważ nie będzie dopasowania połówek klocków znajdujących się na obydwu końcach łańcucha:

Kapitan jest bardzo zły, kiedy poświęca sporo czasu na ułożenie domina a okazuje się, że nie ma możliwości ułożenia danego zestawu. Twoim zadaniem jest pomóc kapitanowi pisząc program, który odpowie na pytanie czy jest możliwość ułożenia danego zestawu domina.

Dane wejściowe:

Dane wejściowe składają się z K zestawów danych. W pierwszym wierszu wejścia znajduje się liczba zestawów danych.

W pierwszym wierszu zestawu danych znajduje się liczba całkowita N (1 ≤ N ≤ 100 000) będąca liczbą klocków w zestawie domina. Kolejnych N wierszy zawiera opisy klocków. Jeden wiersz zawiera dwie liczby całkowite L1 i L2 (1 ≤ L1, L2 ≤ 5 000) oddzielone spacją, będące liczbami znajdującymi się na obydwu połówkach klocka.

Dane wyjściowe:

Dane wyjściowe składają się z K wierszy. Jeden wiersz odpowiada jednemu zestawowi danych wejściowych i zawiera słowo "TAK", jeżeli istnieje możliwość ułożenia domina, lub słowo "NIE" w przeciwnym przypadku.

Przykładowe dane wejściowe:

6
1
3 3
1
3 2
7
2 3
1 1
2 4
1 3
3 4
4 1
2 2
7
1 3
3 4
2 3
2 5
4 2
1 2
3 5
7
1 7
2 7
2 1
3 6
6 4
3 4
4 4
7
1 2
2 3
3 1
1 4
4 5
5 6
6 4
	

Przykładowe dane wyjściowe:

TAK
NIE
NIE
TAK
NIE
NIE