eolymp
bolt
Try our new interface for solving problems
Problems

Blockade

Blockade

Time limit 1 second
Memory limit 64 MiB

State Flatland is a rectangle composed of individual tiles. Flatland is divided into provinces, K (2K100). Each province is a connected set of squares, ie each point of the province can reach any point of it at the same time allowed to move from square to square, only if they have a common side (not the common vertex). In Flatland is not the point, which is bordered to more than three provinces (ie, four square, with a common vertex can not belong to four different provinces).

Each province has its own character. Flatland is the capital of the province, which belongs to the symbol A (a capital letter A). The province is called the border if it contains the boundary squares. The province, which is the capital of Flatland, not a border.

King of the neighboring kingdom with Flatland Flatland Rektilaniya decided to conquer. To do this, he wants to seize the capital Flatland. But he knows that the strength of his army is not enough to make it right. At first he wants to surround the capital province in order to weaken the enemy a long siege, and then seize the capital.

To surround the province, want to capture all the provinces, which it borders. The two provinces border if there are two squares, are side by side, one of which belongs to the first of them, and another - the second one. To capture the province, have to satisfy one of two conditions: either it is the border, or borders with any already captured the province.

To preserve the strength of his army, the king wants to establish a blockade Rektilanii capital province, taking as little as possible provinces. Help him figure out how much you want to capture the provinces. Capture capital province can not, since it forces the Army Rektilanii not enough.

Input data

The first line contains M and N (3M, N200). The following M lines contains N symbols, each card set and Flatland. Symbol, located in the i+1-th line of the input file to the j-th place, is a symbol of the province, which belongs to the square (i, j). All characters are ASCII-code is greater than 32 (space).

Output data

Output a single number - the number of provinces that want to capture. If you can not establish a blockade, output "–1".

Examples

Input example #1
5 6
BBBBBZ
BCCCBZ
BCAbbZ
BDDDbZ
�����Z
Output example #1
4