Pejntbrasz

Time limit1sMemory limit128 MB

Summary

The task is to find the fewest flood fills that make a black and white picture one color.

Level: Medium7 of 10
Topics: Graph, BFS, Shortest path
Solved: No attempts yet

Problem

Karolek got a computer as a Christmas present. Unfortunately he forgot to ask Santa for some games in his letter, so he had to make do with Minesweeper and Solitaire. Recently, though, he discovered one more program that turned out to be far more interesting than those two.

That program is Pejntbrasz, a simple drawing tool. It lets you create rectangular black-and-white pictures. A picture of size $h \times w$ is made of $h \times w$ square pixels. Karolek liked the bucket-fill tool the most, and it inspired him to invent a new game. The rules are simple: given a black-and-white picture, use as few bucket-fill operations as possible to make every pixel the same color.

Write a program that, for a given picture, computes the minimum number of fill operations needed to finish the game.

Detailed description of the bucket-fill tool

Two pixels are adjacent if they share an edge. Two pixels $p_A$ and $p_B$ are connected if there is a sequence of same-colored pixels $p_A = p_0, p_1, \dots, p_k = p_B$ such that $p_i$ and $p_{i+1}$ are adjacent for every $0 \le i < k$ . A region is a maximal set of connected pixels. To use the bucket-fill tool you pick one pixel of the picture; as a result, every pixel of the region that the chosen pixel belongs to changes color.

Input

The first line contains two positive integers $h$ and $w$ , the height and width of the picture. The number of pixels in the picture does not exceed $500$ (that is, $h \times w \le 500$ ). Each of the next $h$ lines describes the picture and contains $w$ characters ('.' for a white pixel, 'X' for a black pixel).

Output

Print, on a single line, the minimum number of fill operations needed to finish Karolek's game.

Examples1

Example 1
Input
```
4 7
..X.X.X
...XXX.
.X..XX.
.....XX
```
Expected output
```
2
```