Nam châm đơn cực

Nam châm đơn cực là nam châm chỉ có một cực, hoặc cực bắc hoặc cực nam. Trong thực tế chúng không tồn tại, nhưng đây là một bài toán lập trình nên ta cứ giả sử là có.

Cho một lưới $n\times m$ ô. Ban đầu bạn được đặt vào các ô một số nam châm cực bắc và một số nam châm cực nam. Số lượng nam châm đặt vào là tuỳ ý, thậm chí nhiều nam châm có thể nằm chung một ô.

Một thao tác được thực hiện như sau: chọn một nam châm cực bắc và một nam châm cực nam để kích hoạt. Nếu chúng nằm cùng hàng hoặc cùng cột và ở hai ô khác nhau thì nam châm cực bắc dịch chuyển một ô về phía nam châm cực nam. Ngược lại, nếu chúng nằm cùng một ô hoặc không chung hàng cũng không chung cột thì không có gì thay đổi. Nam châm cực nam luôn đứng yên.

Mỗi ô của lưới được tô màu đen hoặc trắng. Hãy xét các cách đặt nam châm sao cho đồng thời thoả mãn:

1. Mỗi hàng và mỗi cột đều có ít nhất một nam châm cực nam.
2. Với mỗi ô màu đen, tồn tại một dãy thao tác đưa được một nam châm cực bắc tới ô đó.
3. Với mỗi ô màu trắng, không có dãy thao tác nào đưa được nam châm cực bắc tới ô đó.

Hãy xác định xem có cách đặt nam châm nào thoả mãn cả ba điều kiện hay không. Nếu có, hãy tìm số nam châm cực bắc ít nhất cần dùng (số nam châm cực nam không bị giới hạn).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ là số hàng và số cột của lưới.
• $n$ dòng tiếp theo mô tả màu của lưới. Dòng thứ $i$ là một xâu độ dài $m$, ký tự thứ $j$ cho biết màu của ô ở hàng $i$ cột $j$. Ký tự # là ô đen, ký tự . là ô trắng. Dữ liệu bảo đảm xâu chỉ gồm hai loại ký tự này.

Dữ liệu ra

In ra một số nguyên duy nhất là số nam châm cực bắc ít nhất cần dùng.

Nếu không tồn tại cách đặt nam châm thoả mãn, in ra $-1$.

Ràng buộc

• $1\le n,m\le 1000$

Ví dụ