Ninja

Limit pamięci: 64 MB

Dwóch mistrzów ninja, Takeshi Bajtanamura i Matsuo Bitezuki, postanowiło zmierzyć się w zawodach w byciu niewidocznym. Teren rozgrywki to duży las (który będziemy traktować jak płaszczyznę euklidesową), w którym rośnie drzew (punktowych, rzecz jasna). Ninja będą przemykać od drzewa do drzewa po liniach prostych, pozostając oczywiście ukrytymi przed oczyma postronnych (schowanie się za punktowym drzewem nie jest dla mistrza żadnym wyzwaniem). Każdy z mistrzów ma przypisane drzewo startowe, w którym rozpoczyna, i drzewo, do którego musi dotrzeć.

Twoim zadaniem jest wyznaczenie tras mistrzów. Każda z nich musi być zgodna z regułami gry (czyli być łamaną, której wierzchołkami są niektóre drzewa). Trasy mistrzów nie mogą się krzyżować, ani mieć żadnych punktów wspólnych — to jeszcze nie czas na ostateczną konfrontację!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita oznaczająca liczbę zestawów testowych. Po niej następują zestawy w następującej postaci:

Pierwsza linia zestawu zawiera liczbę całkowitą () — liczbę drzew na terenie gry. W kolejnych liniach podane są pary liczb całkowitych , () – współrzędne kolejnych drzew. Pierwsze i drugie z kolei drzewo to odpowiednio początek i koniec drogi pierwszego mistrza, trzecie i czwarte — drugiego mistrza. Możesz założyć, że żadne dwa drzewa nie rosną w tym samym miejscu oraz żadne trzy drzewa nie leżą na jednej prostej.

Wyjście

Dla każdego zestawu należy wypisać w osobnej linii słowo TAK, jeśli można wytyczyć drogi mistrzów, NIE, jeśli jest to niemożliwe.

Przykład

Dla danych wejściowych:

2
5
201 2
104 302
1 99
410 320
210 201
5
201 2
104 302
1 99
210 201
410 320

poprawną odpowiedzią jest:

NIE
TAK

Autor zadania: (pomysł zapożyczony).