Three states#1061
Three states are located on a rectangular map of size n \times m. It is guaranteed that within each state, it is possible to move from any cell of this state to any other cell of the same state, moving only horizontally or vertically through cells belonging to that state. The cells of each state are marked with one of the numbers (1, 2, or 3).
There are passable (.) and impassable (#) cells on the map.
Build roads in the minimum number of passable cells so that it becomes possible to reach from any cell of one state to any cell of another state. You may freely move within any single state. You can only move horizontally or vertically on the map.
The first line contains the size of the map and (1 \leq n, m \leq 1000). Each of the next lines contains characters:
1, 2, 3 — cells belonging to the states;
. — passable cell, you may build a road here;
# — impassable cell, you cannot build a road here.
Print the minimum number of cells in which roads should be built so that all cells of all states become connected. If it is impossible, print -1.
Example 1