Game of Tiles

Time limit1sMemory limit128 MB

Summary

Two players alternately extend a path of numbered tiles on a grid with blocked cells; the player unable to move loses. Determine the winner under optimal play.

Level: Hard8 of 10
Topics: Graph, Game theory, Dynamic programming, Backtracking
Solved: No attempts yet

Problem

The Game of Tiles is a two-player game played on a rectangular board of $R$ rows and $C$ columns of square cells called tiles. At the start of the game some tiles may be painted black and the rest are white. Player 1 and Player 2 then take turns; the first player who cannot make a valid move loses.

Player 1 moves first. The first move consists of choosing a white tile and writing the number $1$ on it. Each subsequent move $i$ consists of writing the number $i$ on an unused white tile that is horizontally or vertically adjacent (never diagonally) to the tile numbered $i-1$ . Thus Player 1 always writes the odd numbers and Player 2 always writes the even numbers.

Given the initial configuration of the board, determine which player wins if both play optimally.

Input

The input contains several test cases and is read until end of file. Each test case is described using several lines. The first line contains two integers $R$ and $C$ ( $1 \le R, C \le 50$ ), the number of rows and columns of the board. Each of the next $R$ lines contains a string of $C$ characters describing one row of the initial board: the character '.' denotes a white tile and the uppercase letter 'X' denotes a black tile. In every test case at least one tile is white.

Output

For each test case, output a single line containing the number of the player (1 or 2) who wins the game when both play optimally.

Examples4

Example 1

Input

3 4
....
XX.X
...X
3 4
....
.X.X
...X
3 4
....
.X.X
....
1 1
.
1 11
....X......

Expected output

Example 2
Input
```
1 1
.
```
Expected output
```
1
```
Example 3
Input
```
1 2
..
```
Expected output
```
2
```
Example 4
Input
```
2 2
..
..
```
Expected output
```
2
```