Reconstructing a Rectangle from Convex Polygons

A 5-year-old boy, P, is fascinated by paper cutting. He always cuts a rectangular piece of paper into several convex polygons. However, after every cut, he worries that some pieces might have been lost. To verify his work, he tries to reassemble all the convex polygon pieces. If they can perfectly form a rectangle, he concludes that no piece is missing.

You are given the descriptions of these convex polygons by their vertex coordinates in counter-clockwise order. The original rectangular paper is axis-aligned. Your task is to determine if the given pieces can be reassembled to form an exact rectangle without any gaps or overlaps.

The following criteria must be satisfied for a correct reconstruction:

• The total area of all the pieces equals the area of the bounding rectangle formed by the outermost coordinates.
• The only four vertices that appear an odd number of times (when considering all polygon vertices and canceling out shared ones) must coincide with the four corners of the bounding rectangle.

The area of a polygon with vertices \( (x_i, y_i) \) (given in order) is computed by the formula:

[ \text{Area} = \frac{1}{2} \left| \sum_{i=1}^{m} (x_i,y_{i+1} - x_{i+1},y_i) \right|, \quad \text{with} ; (x_{m+1},y_{m+1}) = (x_1,y_1). ]

inputFormat

The first line contains an integer \( n \) (\( 1 \le n \le 100 \)), which is the number of convex polygons.

Then for each of the following \( n \) polygons:

• The first line contains an integer \( m \) (\( 3 \le m \le 10 \)), the number of vertices of the polygon.
• Each of the next \( m \) lines contains two integers \( x \) and \( y \) (\( |x|, |y| \le 10^4 \)), representing the coordinates of a vertex.

The vertices of each polygon are given in counter-clockwise order.

outputFormat

Output a single line containing YES if the convex polygons can be reassembled to form an exact rectangle without gaps or overlaps, and NO otherwise.

sample

1
4
0 0
0 2
3 2
3 0

YES