CF590C.Three States

The famous global economic crisis is approaching rapidly, so the states of Berman, Berance, and Bertaly formed an alliance and allowed the residents of all member states to freely pass through the territory of any of them. In addition, it was decided that a road between the states should be built to guarantee that one could reach any point of any country from any point of any other state.

Since roads are always expensive, the governments of the states of the newly formed alliance asked you to help them assess the costs. To do this, you have been issued a map that can be represented as a rectangular table consisting of $n$ rows and $m$ columns. Any cell of the map either belongs to one of three states, or is an area where it is allowed to build a road, or is an area where the construction of the road is not allowed. A cell is called passable if it belongs to one of the states, or the road was built in this cell. From any passable cells, you can move up, down, right, and left, if the cell that corresponds to the movement exists and is passable.

Your task is to construct a road inside a minimum number of cells so that it would be possible to get from any cell of any state to any cell of any other state using only passable cells.

It is guaranteed that initially it is possible to reach any cell of any state from any cell of this state, moving only along its cells. It is also guaranteed that for any state there is at least one cell that belongs to it.

著名的全球经济危机正迅速逼近，因此伯曼（Berman）、贝朗斯（Berance）和贝尔塔利（Bertaly）三国结成联盟，并允许所有成员国居民自由穿越任一成员国的领土。此外，还决定在各国之间修建道路，以确保从任意一国的任意一点出发，均可到达其余任一国的任意一点。

由于道路建设成本高昂，新联盟各国政府请你协助评估相关费用。为此，你获得了一张可表示为 $n$ 行 $m$ 列矩形表格的地图。地图中每个单元格要么属于三个国家之一，要么是允许修建道路的区域，要么是禁止修建道路的区域。若一个单元格属于某国，或已在其中修建了道路，则称其为可通行单元格。从任意可通行单元格出发，均可向上、下、左、右四个方向移动，前提是目标单元格存在且为可通行单元格。

你的任务是在尽可能少的单元格内修建道路，使得仅通过可通行单元格即可从任意一国的任意单元格到达其余任一国的任意单元格。

题目保证：初始状态下，仅通过某国自身所属的单元格，即可从该国任意单元格到达该国其余任意单元格；且每个国家至少包含一个单元格。

The first line of the input contains the dimensions of the map $n$ and $m$ ($1 \leq n, m \leq 1000$) — the number of rows and columns respectively.

Each of the next $n$ lines contains $m$ characters, describing the rows of the map. Digits from $1$ to $3$ represent the accessory to the corresponding state. The character '.' corresponds to the cell where it is allowed to build a road, and the character '#' means no construction is allowed in this cell.

输入的第一行包含地图的尺寸 $n$ 和 $m$（$1 \leq n, m \leq 1000$），分别表示行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符，描述地图的各行。数字 $1$ 至 $3$ 表示该格子所属的对应州；字符 '.' 表示允许在此格子修建道路；字符 '#' 表示此格子禁止修建道路。

Print a single integer — the minimum number of cells you need to build a road inside in order to connect all the cells of all states. If such a goal is unachievable, print $-1$.

输出一个整数——为连接所有国家的单元格所需修建道路的最少单元格数量。如果该目标无法实现，则输出 $-1$。