Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Gra w wielokąty (gra)

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.