Maximizing the Nesting Chain of Good Polygons

A good polygon is defined as a simple polygon whose sides are parallel to one of the coordinate axes and whose vertices all lie on integer grid points. You are given n good polygons. Their boundaries do not intersect or even touch each other. Although they may be nested (one polygon completely containing another), there exists one polygon that contains all the others; we call it the boundary.

The score of the picture is defined as the maximum length k of a sequence \(a_1,a_2,\dots,a_k\) chosen from the polygons (both the given ones and the ones you add) satisfying

[ \forall; 1\le i<k,\quad a_i \text{ contains } a_{i+1} ]

You are allowed to add several new good polygons inside the boundary polygon, with the condition that after adding them, every pair of polygon boundaries (both original and added) remain non-intersecting and non-touching. Your task is to maximize the score after the additions. You only need to output this maximum score.

Note: A polygon P is considered to contain another polygon Q if Q lies completely inside P (boundaries not touching).

---

Input Format

The first line contains an integer n, the number of polygons. Then for each polygon, the input is given in the following format:

m
x1 y1 x2 y2 ... xm ym

Here, m is the number of vertices of the polygon, and each of the following m pairs are the coordinates of the vertices given in order (either clockwise or counterclockwise). All vertices are at integer coordinates. It is guaranteed that exactly one polygon (the boundary) contains all the others.

---

Output Format

Output a single integer which is the maximum possible score after optimally adding new good polygons inside the boundary.

---

Problem Explanation

You can add extra good polygons inside the fixed boundary polygon. Since two polygon boundaries must not touch, if the boundary polygon is a rectangle with lower left corner \((x_{min}, y_{min})\) and upper right corner \((x_{max}, y_{max})\), then an added polygon must be completely inside, for example with vertices (\(x_{min}+1, y_{min}+1\)) and (\(x_{max}-1, y_{max}-1\)) for its bounding box.

In general, if the boundary polygon has a bounding box of width \(W=x_{max}-x_{min}\) and height \(H=y_{max}-y_{min}\), let \(d=\min(W,H)\). Then one may notice that the maximum number of nested polygons (including the boundary itself) that can be constructed is given by

[ score = \left\lfloor \frac{d-1}{2} \right\rfloor + 1. ]

Your task is to find the boundary polygon (the one with maximum area), determine its bounding box, compute \(d\) and then output the maximum chain length as shown above.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 105), representing the number of polygons. It is followed by n blocks, each describing a polygon. For each polygon:

 m
 x1 y1 x2 y2 ... xm ym

where m (the number of vertices) and the m pairs of integers are given. All coordinates are integers.

outputFormat

Output a single integer — the maximum possible score (i.e. the length of the longest chain of nested polygons) after you add the new good polygons optimally inside the boundary.

sample

1
4
0 0 5 0 5 5 0 5

3