408367: GYM103107 G Go? No

NoGo is a game whose rules are the reverse of Go. In this game, the player who takes opponent's chess pieces or kills his own pieces will lose the game.

Little G is writing a bot to play the game. And he is now working on a simplified version of this game. In the simplified version, Little G has a chess board of size $$$n \times m$$$. There are only two kinds of state in each intersection: empty or occupied by his stone. Two intersections are considered connected if they are orthogonally adjacent (up, down, left, or right). He believes that the more connected components of empty positions his stones can separate, the greater chance he will have to win.

Now you are given the state of chess board at some point. You need to place one stone into an empty intersection and make the number of separated empty connected components as large as possible after placing your stone.

The first line contains two integers $$$n$$$ and $$$m ~ (1 \leq n, m \leq 2000)$$$, indicating the number of rows and columns of the chess board.

Then $$$n$$$ lines follows, each line contains a string of length $$$m$$$ indicating the state of each position in the chess board. A character of "$$$\texttt{#}$$$" represents an occupied position and a character of "$$$\texttt{.}$$$" represents an empty position. It is guaranteed that at least one position is empty.

Output one line with only one integer – the maximum empty connected component you can get after placing one stone into current chess board.

3 3
#..
#.#
..#

2

4 4
#.##
.#.#
...#
.#.#

4

For the first sample, one possible method is to place the stone into intersection $$$(2, 2)$$$ (indexed form $$$1$$$) and get two empty connected components.

For the second sample, one possible method is to place the stone into intersection $$$(3, 1)$$$ and get four empty connected components.