Landlocked

Canada is not landlocked. It touches the ocean, and in fact it touches three of them.

There are 46 countries in the world that are landlocked, Bolivia and Mongolia among them. A landlocked country does not touch an ocean, but it reaches one by passing through a single other country. A person in Mongolia reaches an ocean by passing through Russia.

Liechtenstein and Uzbekistan are the only two land-landlocked countries in the world. They are landlocked, and every country that surrounds them is landlocked as well. Anyone leaving Uzbekistan therefore passes through at least two different countries before reaching an ocean.

Given a map, determine how landlocked each country is. A country is not landlocked, recorded as $0$, if any of its cells has water in a horizontally, vertically, or diagonally adjacent cell. If a country is landlocked, its value is the smallest number of borders that must be crossed to travel from the country to water. Each step of the journey moves to a horizontally, vertically, or diagonally adjacent cell. Crossing a border means stepping from a cell of one country into a cell of a different country. A water cell belongs to no country, so stepping into water does not count as crossing a border.

A country may be split into several pieces, the way a country made of islands is. Its value is then the smallest of the values computed for its pieces.

The first line contains $N$ and $M$. ($1 \le N, M \le 1000$)

Each of the next $N$ lines contains $M$ uppercase letters with no spaces between them. Each country is written with its own letter. The letter W is not used as a country name; it marks the water of an ocean, a sea, or a lake. The map contains at least one water cell.

For each country on the map, print one line holding the letter of the country and its value, separated by a single space. Print the countries in alphabetical order.