Submit | All submissions | Best solutions | Back to list |

## POLYGAME - The Game of Polygons |

Two players take part in the game **polygons**. A convex polygon with * n* vertices divided by
* n-3* diagonals into * n-2* triangles is necessary.
These diagonals may intersect in vertices of the polygon only. One of the triangles is black and the
remaining ones are white. Players proceed in alternate turns. Each player, when
its turn comes, cuts away one
triangle from the polygon. players are allowed to cut off triangles along the given
diagonals. The winner is the player who cuts away the black triangle.

NOTE: We call a polygon ** convex** if a segment joining any two points of
the polygon is contained in the polygon.

### Task

Write a program which:

- reads from the standard input the description of the polygon,
- verifies whether the player who starts the game has a winning strategy,
- writes the result to the standard output.

### Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.
The first line of each test case contains an integer *n*,* 4 <= n <=
50000*. This is the number of vertices in the polygon. The vertices of the polygon
are numbered, clockwise, from
* 0* to *n-1*.

The next * n-2* lines comprise descriptions of triangles in the polygon. In the*
i+1*-th line, * 1 <= i <= n-2*, there are three non-negative
integers *a, b, c*
separated by single spaces. Theses are numbers of vertices of the *i*-th triangle. The first triangle in a
sequence is black.

### Output

The output for each test case should have one line with the word:

- YES, if the player, who starts the game has a winning strategy,
- NO, if he does not have a winning strategy.

### Example

Sample input:1 6 0 1 2 2 4 3 4 2 0 0 5 4Sample output:YES

**Warning: large Input/Output data, be careful with certain languages**

Added by: | Piotr Łowiec |

Date: | 2004-09-13 |

Time limit: | 7s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C C++ 4.3.2 CPP CPP14 CPP14-CLANG FORTRAN JAVA NODEJS PERL6 PERL PHP PROLOG PYTHON PYTHON3 RUBY TCL |

Resource: | 6th Polish Olympiad in Informatics, stage 1 |