Description

You are given $n$ pairwise disjoint polygons. All edges of these polygons are parallel or perpendicular to the coordinate axes. Define the depth $d_i$ of polygon $i$ as $\max\{d_j\}+1$, where polygon $j$ contains polygon $i$. In particular, if a polygon is not contained in any other polygon, then its depth is $1$. Find the depth of the polygon with the maximum depth.

Input Format

The first line contains a positive integer $n$.

Each of the following lines describes one polygon. First, an even integer $k$ $(4 \leqslant k \leqslant 10000)$ is given, followed by $k$ integers: $x_1,x_2,\cdots,x_k$ $(0 \leqslant x_i \leqslant 10^8)$. The coordinates of the points are $(x_1, x_2), (x_3, x_2), (x_3, x_4), (x_5, x_4),\cdots,(x_{k-1}, x_k), (x_1, x_k)$. They form the polygon in counterclockwise order.

Output Format

Output one integer, the maximum depth.

3
4 0 0 10 10
4 3 4 6 8
4 1 1 2 2

2

6
4 1 0 17 12
16 10 4 16 11 2 4 8 2 3 3 2 1 16 3 15 2
8 8 10 3 5 12 8 11 6
6 10 9 15 10 9 7
4 4 6 7 9
4 6 8 5 7

5

Hint

For $100\%$ of the testdata, $n \leqslant 40000, \sum k \leqslant 200000$.

Translated by ChatGPT 5