Cắt hình

Cho một tấm giấy kẻ ô kích thước $n\times m$. Một số ô được tô màu. Gọi $A$ là tập hợp tất cả các ô được tô màu. Đảm bảo tập $A$ khác rỗng và liên thông.

Một tập các ô được tô màu gọi là liên thông nếu với mọi hai ô $a$ và $b$ thuộc tập đó, tồn tại một dãy các ô cùng thuộc tập, bắt đầu từ $a$ và kết thúc ở $b$, sao cho hai ô liên tiếp bất kỳ trong dãy có chung một cạnh. Theo quy ước, tập rỗng và tập chỉ gồm đúng một ô đều được coi là liên thông.

Nhiệm vụ của bạn là tìm số ô ít nhất cần xóa khỏi tập $A$ để tập trở nên không liên thông. Nếu không thể làm cho tập không liên thông, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: kích thước tấm giấy.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả tấm giấy: ký tự thứ $j$ của dòng thứ $i$ là "#" nếu ô tương ứng được tô màu (thuộc $A$), hoặc "." nếu ô không được tô màu.

Dữ liệu ra

In ra một số nguyên: số ô ít nhất cần xóa để tập $A$ trở nên không liên thông, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n,m\le 50$
• Tập $A$ khác rỗng và liên thông.

Ví dụ