축구 경기장

나지예르되(Nagyerdő)는 헝가리 데브레첸 시에 있는 정사각형 모양의 숲으로, $N \times N$ 격자 칸으로 모델링할 수 있다. 행은 북쪽에서 남쪽으로 $0$부터 $N - 1$까지, 열은 서쪽에서 동쪽으로 $0$부터 $N - 1$까지 번호가 매겨진다. 행 $r$, 열 $c$에 있는 칸을 칸 $(r, c)$라고 한다.

숲의 각 칸은 빈 칸이거나 나무가 있는 칸이다. 숲에는 빈 칸이 적어도 하나 있다.

이 도시의 유명 스포츠 클럽인 DVSC가 숲에 새 축구 경기장을 지으려고 한다. 크기가 $s$인 경기장($s \ge 1$)은 서로 다른 빈 칸 $s$개의 집합 $(r_0, c_0), \ldots, (r_{s-1}, c_{s-1})$이며, 모든 $i < j$ 쌍에 대해 $r_i \ne r_j$ 또는 $c_i \ne c_j$ 중 하나 이상이 성립한다.

경기장 칸들 사이로 공을 옮긴다. 직선 킥은 다음 두 가지 동작 중 하나이다.

• 칸 $(r, a)$에서 칸 $(r, b)$로 공을 옮긴다 ($0 \le r, a, b < N$, $a \ne b$). 이때 행 $r$에서 칸 $(r, a)$와 $(r, b)$ 사이의 모든 칸이 경기장에 포함되어 있어야 한다. 형식적으로, $a < b$이면 $a \le k \le b$인 각 $k$에 대해 칸 $(r, k)$가 경기장에 있어야 하고, $a > b$이면 $b \le k \le a$인 각 $k$에 대해 칸 $(r, k)$가 경기장에 있어야 한다.
• 칸 $(a, c)$에서 칸 $(b, c)$로 공을 옮긴다 ($0 \le c, a, b < N$, $a \ne b$). 이때 열 $c$에서 칸 $(a, c)$와 $(b, c)$ 사이의 모든 칸이 경기장에 포함되어 있어야 한다. 형식적으로, $a < b$이면 $a \le k \le b$인 각 $k$에 대해 칸 $(k, c)$가 경기장에 있어야 하고, $a > b$이면 $b \le k \le a$인 각 $k$에 대해 칸 $(k, c)$가 경기장에 있어야 한다.

경기장 안의 임의의 칸에서 다른 임의의 칸으로 직선 킥을 최대 $2$번 사용해 공을 옮길 수 있으면 그 경기장은 정규이다. 크기가 $1$인 경기장은 모두 정규이다.

그림의 예시는 $N = 5$인 숲이며, 나무는 $(1, 0)$과 $(4, 2)$에 있다. 나무가 있는 칸은 검게 칠하고, 경기장에 포함된 칸은 빗금으로 표시했다. 왼쪽 경기장은 정규이다. 가운데 경기장은 칸 $(4, 1)$에서 $(4, 3)$으로 공을 옮기는 데 직선 킥이 적어도 $3$번 필요하므로 정규가 아니다. 오른쪽 경기장도 직선 킥으로 칸 $(3, 0)$에서 $(1, 3)$으로 공을 옮길 수 없으므로 정규가 아니다.

클럽은 가능한 한 큰 정규 경기장을 짓고 싶어 한다. 숲에 존재하는 정규 경기장의 크기 $s$의 최댓값을 구하라.

• $1 \le N \le 2000$
• 모든 $0 \le i < N$, $0 \le j < N$에 대해 $0 \le F[i][j] \le 1$이다.
• 숲에는 빈 칸이 적어도 하나 있다. 즉, 어떤 $0 \le i < N$, $0 \le j < N$에 대해 $F[i][j] = 0$이다.