PUCMM223 - C You and Me

no tags 

You and Me is a board game between two players, the board is MxN, with 1 ≤ M,N ≤ 20. Initially each player has one piece, piece 'a' and piece 'b', both players move at the same time its piece, a valid move is to move the piece one square on each of the 4 cardinal directions (North, South, East, West),or stay in the same square, that is, if a piece is at x,y it can move to(x-1, y), (x, y-1), (x, y), (x, y+1), (x+1, y), so with the two pieces combined there are 5x5=25 possibilities in one move. The game has a goal, piece 'a' must finish at position initially accupied by 'b', and viceversa. To make this game more interesting the cells can be occupied by a block('#'), or can be unocuppied('.'). What is the minimum number of moves required to achieve this goal, if the pieces cannot occupy the same square at a given time and can't cross each other. See examples for further details.

Input

For each test case the first line contains two separated integers, M and N, rows and columns of the board.

then M strings of N characters follow.

Each character could be '.', '#', 'a', 'b'.

Just one 'a' and one 'b' exists.

The last case is followed by 0 0.

Output

Output the minimum number of moves required to achieve the goal. Output IMPOSSIBLE if it is not possible.

Example

Input:
3 4
#..#
a..b
####
3 7
#######
#a...b#
#######
4 4
a...
###.
##..
b...
0 0
Output:

5
IMPOSSIBLE
11

Note:
1st case:
one possibility is
#..# #..# #.b# #..# #..# #..#
a..b--->.ab.--->..a.--->..ba--->.b.a--->b..a
#### #### #### #### #### ####


Added by:Olson Ortiz
Date:2012-07-27
Time limit:0.130s-0.391s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:CSHARP CPP C++ 4.3.2 JAVA
Resource:Used in 3rd PUCMM Olympiad 2012 (1st phase)