Ba Quốc Gia

Cho bản đồ là một bảng hình chữ nhật gồm $n$ hàng và $m$ cột. Mỗi ô trên bản đồ được biểu diễn bằng một ký tự với các ý nghĩa sau:

• Các ký tự 1, 2, 3 biểu thị ô thuộc về quốc gia tương ứng (1, 2 hoặc 3).
• Ký tự . biểu thị một ô trống có thể xây đường đi qua.
• Ký tự # biểu thị một ô không thể xây đường (cấm xây).

Một ô được gọi là đi được nếu nó thuộc về một trong ba quốc gia, hoặc đã được xây đường tại đó. Từ một ô đi được, ta có thể di chuyển sang ô đi được liền kề theo bốn hướng lên / xuống / trái / phải, miễn là ô đó tồn tại trong bảng.

Hãy tìm số lượng ô tối thiểu cần xây đường (chỉ được xây trên các ô .) sao cho từ một ô bất kỳ của một quốc gia có thể đi tới một ô bất kỳ của hai quốc gia còn lại thông qua các ô đi được. Nếu không thể đạt được mục tiêu, in ra $-1$.

Đảm bảo rằng ban đầu các ô cùng thuộc một quốc gia đã liên thông với nhau (chỉ đi qua các ô của quốc gia đó), và mỗi quốc gia có ít nhất một ô trên bản đồ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1\le n,m\le 1000$) — số hàng và số cột.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự mô tả các hàng của bản đồ.

Dữ liệu ra

In ra một số nguyên duy nhất — số ô tối thiểu cần xây đường, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n,m\le 1000$
• Mỗi ký tự trên bản đồ thuộc tập $\{$1, 2, 3, ., #$\}$.
• Các ô cùng quốc gia ban đầu đã liên thông; mỗi quốc gia có ít nhất một ô.

Ví dụ