Dots and Boxes

Alice and Bob play Dots and Boxes on a square lattice of $N \times N$ dots. They move alternately. One move draws a segment between two dots that are neighbours horizontally or vertically and are not connected yet. When four segments close a unit square, the player who drew the last of those four segments scores one point for that square. The game ends once every possible segment has been drawn, and the player with more points wins.

Today the two are not in a competitive mood, so neither follows a strategy. Even when a move would score a point, a player can leave it and play somewhere else. They have been playing for a while and neither has scored yet. If nobody scores soon, they will get bored.

You are given the current position. Let $k$ be the largest number of moves that can still be played without closing a single square. After those $k$ moves every remaining segment closes a square, so the move numbered $k + 1$ scores a point. Print $k + 1$, the number of moves that can be made in the worst case before Alice or Bob has certainly scored.

The first line contains one integer $N$ ($2 \le N \le 80$), the number of dots along one side of the lattice.

The next $2N - 1$ lines contain $2N - 1$ characters each and describe the current position in row major order. Rows and columns are numbered from $1$.

• Cell $(2i - 1, 2j - 1)$ is * and marks dot $(i, j)$, for $1 \le i \le N$ and $1 \le j \le N$.
• Cell $(2i - 1, 2j)$ is - when dots $(i, j)$ and $(i, j + 1)$ are connected by a segment, and . otherwise, for $1 \le i \le N$ and $1 \le j \le N - 1$.
• Cell $(2i, 2j - 1)$ is | when dots $(i, j)$ and $(i + 1, j)$ are connected by a segment, and . otherwise, for $1 \le i \le N - 1$ and $1 \le j \le N$.
• Cell $(2i, 2j)$ is ., for $1 \le i \le N - 1$ and $1 \le j \le N - 1$.

No unit square is closed in the given position, so neither player has scored.

Print one integer, the number of moves that can be made in the worst case before Alice or Bob has certainly scored a point.