{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"F-Go? No \n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eNoGo\u003c/span\u003e is a game whose rules are the reverse of \u003cspan class\u003d\"tex-font-style-it\"\u003eGo\u003c/span\u003e. In this game, the player who takes opponent\u0027s chess pieces or kills his own pieces will lose the game.\u003c/p\u003e\n\u003cp\u003eLittle 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.\u003c/p\u003e\n\u003cp\u003eNow 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cp\u003eThen $$$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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one line with only one integer – the maximum empty connected component you can get after placing one stone into current chess board.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3 3\n#..\n#.#\n..#\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e2\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 4\n#.##\n.#.#\n...#\n.#.#\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e4\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eFor the first sample, one possible method is to place the stone into intersection $$$(2, 2)$$$ (indexed form $$$1$$$) and get two empty connected components.\u003c/p\u003e\n\u003cp\u003eFor the second sample, one possible method is to place the stone into intersection $$$(3, 1)$$$ and get four empty connected components.\u003c/p\u003e"}}]}