Soccer Stadium

Nagyerdő is a square-shaped forest located in the city of Debrecen, which can be modeled as an $N \times N$ grid of cells. The rows are numbered from $0$ to $N - 1$ from north to south, and the columns are numbered from $0$ to $N - 1$ from west to east. The cell at row $r$ and column $c$ is called cell $(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 sports club of the city, plans to build a new soccer stadium in the forest. A stadium of size $s$ (where $s \ge 1$) is a set of $s$ distinct empty cells $(r_0, c_0), \ldots, (r_{s-1}, c_{s-1})$ such that for every pair $i < j$, at least one of $r_i \ne r_j$ and $c_i \ne c_j$ holds.

A ball is moved around the cells of the stadium. A straight kick is either of the following two actions:

• Move the ball from cell $(r, a)$ to cell $(r, b)$ ($0 \le r, a, b < N$, $a \ne b$), where the stadium contains all cells between cell $(r, a)$ and $(r, b)$ in row $r$. Formally, if $a < b$ then the stadium contains cell $(r, k)$ for each $k$ with $a \le k \le b$, and if $a > b$ then the stadium contains cell $(r, k)$ for each $k$ with $b \le k \le a$.
• Move the ball from cell $(a, c)$ to cell $(b, c)$ ($0 \le c, a, b < N$, $a \ne b$), where the stadium contains all cells between cell $(a, c)$ and $(b, c)$ in column $c$. Formally, if $a < b$ then the stadium contains cell $(k, c)$ for each $k$ with $a \le k \le b$, and if $a > b$ then the stadium contains cell $(k, c)$ for each $k$ with $b \le k \le a$.

A stadium is regular if the ball can be moved from any cell in the stadium to any other cell in the stadium using at most $2$ straight kicks. Any stadium of size $1$ is regular.

In the example figure, cells with trees are darkened and cells in the stadium are striped, for a forest of size $N = 5$ with trees at $(1, 0)$ and $(4, 2)$. The stadium on the left is regular. The stadium in the middle is not regular, because at least $3$ straight kicks are needed to move the ball from cell $(4, 1)$ to $(4, 3)$. The stadium on the right is also not regular, because the ball cannot be moved from cell $(3, 0)$ to $(1, 3)$ using straight kicks.

The club wants to build a regular stadium that is as large as possible. Find the maximum $s$ such that a regular stadium of size $s$ exists in the forest.

• $1 \le N \le 2000$
• $0 \le F[i][j] \le 1$ for each $i$ and $j$ with $0 \le i < N$ and $0 \le j < N$.
• There is at least one empty cell in the forest. In other words, $F[i][j] = 0$ for some $0 \le i < N$ and $0 \le j < N$.