human
A monopole magnet is a magnet that only has one pole, either north or south. They don't actually exist since real magnets have two poles, but this is a programming contest problem, so we don't care.

There is an n× m grid. Initially, you may place some north magnets and some south magnets into the cells. You are allowed to place as many magnets as you like, even multiple in the same cell.

An operation is performed as follows. Choose a north magnet and a south magnet to activate. If they are in the same row or the same column and they occupy different cells, then the north magnet moves one unit closer to the south magnet. Otherwise, if they occupy the same cell or do not share a row or column, then nothing changes. Note that the south magnets are immovable.

Each cell of the grid is colored black or white. Let's consider ways to place magnets in the cells so that the following conditions are met.

  1. There is at least one south magnet in every row and every column. 
  2. If a cell is colored black, then it is possible for a north magnet to occupy this cell after some sequence of operations from the initial placement. 
  3. If a cell is colored white, then it is impossible for a north magnet to occupy this cell after some sequence of operations from the initial placement. 


Determine if it is possible to place magnets such that these conditions are met. If it is possible, find the minimum number of north magnets required (there are no requirements on the number of south magnets).

Input

The first line contains two integers n and m (1≤ n,m≤ 1000) — the number of rows and the number of columns, respectively.

The next n lines describe the coloring. The i-th of these lines contains a string of length m, where the j-th character denotes the color of the cell in row i and column j. The characters "#" and "." represent black and white, respectively. It is guaranteed, that the string will not contain any other characters.

Output

Output a single integer, the minimum possible number of north magnets...
Solve the task in PYTHON.
assistant
#Here is Python code to find the minimum number of north magnets required (there are no requirements on the number of south magnets).

from __future__ import division, print_function
_interactive = False

def main():
    n, m = input_as_list()
    g = [input() for _ in range(n)]

    from itertools import chain, groupby
    for line in chain(g, zip(*g)):
        if sum(k=="#" for k, _ in groupby(line)) > 1:
            print(-1)
            return

    if all(("#" in row) for row in g) ^ all(("#" in col) for col in zip(*g)):
        print(-1)
        return

    N = n*m
    p = list(range(N))
    r = array_of(int, N)

    def find(a):
        acopy = a
        while p[a] != a:
            a = p[a]
        while acopy != a:
            p[acopy] = p[a]
            acopy = p[acopy]
        return p[a]

    def union(a, b):
        a, b = find(a), find(b)
        if a == b: return
        if r[a] < r[b]: a, b = b, a
        if r[a] == r[b]: r[a] += 1
        p[b] = a

    for i in range(n):
        for j in range(m):
            if g[i][j] == '#':
                if i != 0 and g[i-1][j] == '#':
                    union(i*m+j, (i-1)*m+j)
                if i != n-1 and g[i+1][j] == '#':
                    union(i*m+j, (i+1)*m+j)
                if j != 0 and g[i][j-1] == '#':
                    union(i*m+j, i*m+j-1)
                if j != m-1 and g[i][j+1] == '#':
                    union(i*m+j, i*m+j+1)

    roots = set()
    for i in range(n):
        for j in range(m):
            if g[i][j] == '#':
                roots.add(find(i*m+j))

    print(len(roots))

# Constants
INF = float('inf')
MOD = 10**9+7
alphabets = 'abcdefghijklmnopqrstuvwxyz'

# Python3 equivalent names
import os, sys, itertools
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

# print-flush in interactive problems
if _interactive:
    flush = sys.stdout.flush()
    def printf(*args, **kwargs):
        print(*args, **kwargs)
        flush()

# Debug print, only works on local machine
LOCAL = "LOCAL_" in os.environ
debug_print = (print) if LOCAL else (lambda *x, **y:...