P1488 The Fat Cat's Game

JMcat and PZ are classmates, and both are math whizzes, so it is no surprise that they often discuss math problems together. One day, JMcat found an interesting geometric game and showed it to PZ. The game is played on a convex polygon with $n$ vertices. Its $n-3$ diagonals divide the polygon into $n-2$ triangles, and these $n-3$ diagonals intersect at the polygon’s vertices. One of the triangles is colored black, and the others are white. The two players take turns. On your turn, you must cut off one triangle from the polygon along the drawn diagonals. The player who cuts off the black triangle wins. Assume JMcat moves first. Does JMcat have a winning strategy? Please write a program to help JMcat find out.

The first line contains an integer $n$, the number of vertices of the polygon. The vertices are labeled from $0$ to $n-1$ in clockwise order. Each of the next $n-2$ lines describes one of the triangles forming the polygon. Line $i+1$ $(1 \leq i \leq n-2)$ contains three space-separated nonnegative integers $a$, $b$, and $c$, which are the vertex labels of the $i$-th triangle. The first triangle given is black.

Output a single line. If JMcat has a winning strategy, print `JMcat Win`; otherwise, print `PZ Win` (note the case and the space).

Constraints: $4 \leq n \leq 5 \times 10^4$. A polygon is called convex if every line segment connecting any two points of the polygon lies entirely within the polygon. Translated by ChatGPT 5