P5932 [POI 1999 R1] Polygon Battle

Polygon Battle is a two-player game.

The game is played on a convex polygon with $n$ vertices. The polygon is divided into $n - 2$ triangles by $n - 3$ diagonals, and these $n - 3$ diagonals intersect at the vertices of the polygon. One of the triangles is colored black, and the others are white. The two players take turns. On a player's turn, they must cut off one triangle from the polygon along the drawn diagonals. The player who cuts off the black triangle wins. - Note: A polygon is called a convex polygon if the line segment connecting any two points inside the polygon lies entirely within the polygon.

The first line contains an integer $n$, the number of vertices of the polygon. The vertices are numbered clockwise from $0$ to $n - 1$. The next $n - 2$ lines describe the triangles that form the polygon. In the $(i + 1)$-th line $(1 \le i \le n - 2)$, there are three non-negative integers $a, b, c$ separated by spaces. They are the vertex numbers of the $i$-th triangle. The first given triangle is black.

The only line should contain one word: - `TAK`, meaning the first player has a winning strategy. - `NIE`, meaning the first player does not have a winning strategy.

For $100\%$ of the testdata, $4 \le n \le 50000$. Translated by ChatGPT 5