配点 : $1300$ 点

問題文

縦 $N$ 行、横 $N$ 列の正方形状のマス目があります。 上から $i$ 行目、左から $j$ 列目のマスを $(i,\ j)$ と表します。

最初、各マスは白か黒です。 最初のマス目の配色は、正方形状に並ぶ文字 $a_{ij}$ ($1 \leq i,\ j \leq N$) として与えられます。 マス $(i,\ j)$ が白ならば $a_{ij}$ は . であり、黒ならば $a_{ij}$ は # です。

あなたは、マス目の配色を塗り替えるロボットを開発しています。 このロボットは次の操作を繰り返し行うことができます。

• 整数 $i$, $j$ ($1 \leq i,\ j \leq N$) をそれぞれ自由に選ぶ。 マス $(i,\ 1)$, $(i,\ 2)$, $...$, $(i,\ N)$ の色をそれぞれ $c_1$, $c_2$, $...$, $c_N$ として記憶する。 その後、マス $(1,\ j)$, $(2,\ j)$, $...$, $(N,\ j)$ の色をそれぞれ $c_1$, $c_2$, $...$, $c_N$ で塗り替える。

あなたの目標は、すべてのマスを黒にすることです。 すべてのマスを黒にすることが可能か判定し、可能ならば必要な操作回数の最小値を求めてください。

制約

• $2 \leq N \leq 500$
• $a_{ij}$ は . または # である。

部分点

• $300$ 点分のテストケースでは、$N \leq 3$ が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_{11}$$...$$a_{1N}$

$:$

$a_{N1}$$...$$a_{NN}$

出力

すべてのマスを黒にすることが可能ならば、必要な操作回数の最小値を出力せよ。 不可能ならば、代わりに -1 を出力せよ。

2
#.
.#

3

例えば、次のように操作を行うと、次図のようにマス目の配色が変わります。

• $i = 1$, $j = 2$ と選んで操作を行う。
• $i = 1$, $j = 1$ と選んで操作を行う。
• $i = 1$, $j = 2$ と選んで操作を行う。

2
..
..

-1

2
##
##

0

3
.#.
###
.#.

2

3
...
.#.
...

5