Problem H

Siege

 

The kingdom of Flatland can be represented as a rectangle M*N, which consists of squares 1*1. Flatland is divided into K provinces (2£K£100). Each province is a connected set of squares i.e. it’s possible to get from one point of a province to another one. However, it’s allowed to move from square to square if and only if two squares have the same side (having the same vertex is not enough). There is no point in Flatland, which has a boundary with more than three other provinces i.e. four squares, which have the same vertex can’t belong to four different provinces.

 

Each province has its own symbol. The capital of Flatland is situated in the province marked as A (capital Latin A). A province is called a frontier if it contains frontier squares. The capital of Flatland is not frontier.

 

An evil king from the kingdom of Wreckland wants to conquer Flatland. In order to do that he wants, he has to conquer the capital of Flatland. But he knows that his army has not been strong enough to do it at once, capturing all the provinces. So, the evil king decided to surround the capital, to weaken the forces of Flatland by long siege, and then conquer the capital.

 

In order to surround the capital, he should conquer all boundary provinces of it. Two provinces are bordering on each other if there are two squares, which have the same side, one of which belongs to one province, and the other one belongs to the other one. In order to conquer a province, the king should do one of these statements: either it is a frontier province or it is an already conquered province.

 

In order to save his forces (it’s the most important issue on a war!), the king of Wreckland wants to conquer as fewer provinces as he can. Please help him to find out how many provinces he should conquer. The king realizes that he can’t conquer the capital right now, because his army has not been strong enough…

 

Input

There can be multiple test cases. The first line of each test case contains M and N (3 £ M, N £ 200). Next M lines contain N symbols each and give the map of Flatland. The character in i+1-th line in j-th place, represent the square in (i,j). All the symbols have ASCII-code higher than 32(blank). The input ends with a case where M=0 and N=0. You must not process this test case.

 

Output

The only one line of the output contains the only one number – the number of provinces which must be conquered. If it is impossible to conquer the capital, then print “–1”.

 

 

 

 

 

Sample Input

Sample Output

5 6

BBBBBZ

BCCCBZ

BCAbbZ

BDDDbZ

33333Z

3 3

BBB

BAB

BBB

0 0

4

1

 

Problem source: Russian National Team Olympiad 2001

Problem author: Andrew Stankevich

Problem translation: Dmytro Chernysh

Problem solution: Andrew Stankevich, Dmytro Chernysh