Gra w wielokąty

Limit pamięci: 32 MB

W grze w wielokąty uczestniczy dwóch graczy. Rekwizytem jest wielokąt wypukły o n wierzchołkach podzielony przez przekątne na trójkąty. Żadne dwie z tych przekątnych nie przecinają się poza wierzchołkami wielokąta. Jeden z trójkątów jest czarny, a pozostałe - białe. Gracze na przemian odcinają od wielokąta po jednym trójkącie, za każdym razem przecinając wielokąt wzdłuż jednej z danych przekątnych. Gracz, który odetnie czarny trójkąt wygrywa.

PRZYPOMNIENIE: Wielokąt jest wypukły, jeśli odcinek łączący dowolne dwa jego punkty jest całkowicie zawarty w wielokącie.

Zadanie

Napisz program, który:

• czyta ze standardowego wejścia opis rekwizytu do gry,
• sprawdza, czy gracz rozpoczynający grę ma strategię wygrywającą,
• wypisuje wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera liczbę naturalną , . Jest to liczba wierzchołków wielokąta. Wierzchołki wielokąta są ponumerowane kolejnymi liczbami od do , zgodnie z ruchem wskazówek zegara. Następnych wierszy zawiera opisy trójkątów w wielokącie. W wierszu o numerze , , znajdują się trzy liczby naturalne , , oddzielone pojedynczymi odstępami. Są to numery wierzchołków -tego trójkąta. Pierwszy trójkąt w ciągu jest czarny.

Wyjście

Standardowe wyjście powinno składać się z jednego wiersza zawierającego jedno słowo:

• TAK, jeśli gracz rozpoczynający grę ma strategię wygrywającą,
• NIE, jeśli nie ma.

Przykład

Dla danych wejściowych:

6
0 1 2
2 4 3
4 2 0
0 5 4

poprawną odpowiedzią jest:

TAK

Autor zadania: Grzegorz Jakacki.