Soccer Stadium

문제

Nagyerdő is a square-shaped forest located in the city of Debrecen, which can be modeled as an $N\times NN\; \backslash times\; N$ grid of cells. The rows of the grid are numbered from $00$ to $N-1N\; -\; 1$ from north to south, and the columns are numbered from $00$ to $N-1N\; -\; 1$ from west to east. We refer to the cell located at row $rr$ and column $cc$ of the grid as cell $(r,c)(r,\; c)$.

In the forest, each cell is either empty or contains a tree. At least one cell in the forest is empty.

DVSC, the famous sports club of the city, is planning to build a new soccer stadium in the forest. A stadium of size $ss$ (where $s\ge 1s\; \backslash ge\; 1$) is a set of $ss$ distinct empty cells $(r_0,c_0),\dots ,(r_{s-1},c_{s-1})(r\_0,\; c\_0),\; \backslash ldots,\; (r\_\{s\; -\; 1\},\; c\_\{s\; -\; 1\})$.

• for each $ii$ from $00$ to $s-1s\; -\; 1$, inclusive, cell $(r_i,c_i)(r\_i,\; c\_i)$ is empty,
• for each $i,ji,\; j$ such that $0\le i<j<s0\; \backslash le\; i\; \backslash lt\; j\; \backslash lt\; s$, at least one of $r_i\mathrm{\ne }{r}_{j}r\_i\; \backslash neq\; r\_j$ and $c_i\mathrm{\ne }{c}_{j}c\_i\; \backslash neq\; c\_j$ holds.

Soccer is played using a ball that is moved around the cells of the stadium. A straight kick is defined to be either of the following two actions:

• Move the ball from cell $(r,a)(r,a)$ to cell $(r,b)(r,b)$ ($0\le r,a,b<N,a\mathrm{\ne }b0\; \backslash le\; r,a,b\; \backslash lt\; N,\; a\; \backslash ne\; b$), where the stadium contains all cells between cell $(r,a)(r,a)$ and $(r,b)(r,b)$ in row $rr$. Formally,
  • if $a<ba\; \backslash lt\; b$ then the stadium should contain cell $(r,k)(r,k)$ for each $kk$ such that $a\le k\le ba\; \backslash le\; k\; \backslash le\; b$,
  • if $a>ba\; \backslash gt\; b$ then the stadium should contain cell $(r,k)(r,k)$ for each $kk$ such that $b\le k\le ab\; \backslash le\; k\; \backslash le\; a$.
• Move the ball from cell $(a,c)(a,c)$ to cell $(b,c)(b,c)$ ($0\le c,a,b<N,a\mathrm{\ne }b0\; \backslash le\; c,a,b\; \backslash lt\; N,\; a\; \backslash ne\; b$), where the stadium contains all cells between cell $(a,c)(a,c)$ and $(b,c)(b,c)$ in column $cc$. Formally,
  • if $a<ba\; \backslash lt\; b$ then the stadium should contain cell $(k,c)(k,c)$ for each $kk$ such that $a\le k\le ba\; \backslash le\; k\; \backslash le\; b$,
  • if $a>ba\; \backslash gt\; b$ then the stadium should contain cell $(k,c)(k,c)$ for each $kk$ such that $b\le k\le ab\; \backslash le\; k\; \backslash le\; a$.

A stadium is regular if it is possible to move the ball from any cell contained by the stadium to any other cell contained by the stadium with at most $22$ straight kicks. Note that any stadium of size $11$ is regular.

For example, consider a forest of size $N=5N\; =\; 5$, with cells $(1,0)(1,0)$ and $(4,2)(4,2)$ containing trees and every other cell being empty. The figure below shows three possible stadiums. Cells with trees are darkened, and cells contained by the stadium are striped.

The stadium on the left is regular. However, the stadium in the middle is not regular, because at least $33$ straight kicks are needed to move the ball from cell $(4,1)(4,1)$ to $(4,3)(4,3)$. The stadium on the right is also not regular, because it is impossible to move the ball from cell $(3,0)(3,0)$ to $(1,3)(1,3)$ using straight kicks.

The sports club wants to build a regular stadium that is as big as possible. Your task is to find the maximum value of $ss$ such that there exists a regular stadium of size $ss$ in the forest.