Field of dreams

A field is represented by a 2-D grid of size NxM
Each cell in the grid is either a g cell or a d cell, where g denotes grass and d denotes dirt
Two cells are said to be connected if they share an edge
The grid is said to be connected if all the g cells can be traversed without passing through d cells. Otherwise, the grid is said to be disconnected.
Write a program to find the minimum number of g cells that must be replaced by d cells such that grid is disconnected. If the grid is initially disconnected print 0.

Input format

First line N and M
Next N lines: M space-separated characters (g or d)
Output format
Print the minimum number of g cells that must be replaced by d cells such that the grid is disconnected. If the grid is initially disconnected, print 0.

Contraints
1<= N
M <= 400

Sample Input
ggg
gdg
ggg

Sample Output
2

Explanation

You can convert 2 g to d to convert the grid into following:

ggd
gdg
dgg

The grid is no longer connected.