## 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 4a...###.##..b...0 0Output:5IMPOSSIBLE11Note: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 C++ 4.3.2 CPP JAVA Resource: Used in 3rd PUCMM Olympiad 2012 (1st phase)