eolymp
bolt
Try our new interface for solving problems
Problems

Island Buses

Island Buses

Time limit 1 second
Memory limit 64 MiB

The Island Cargo and Passenger Company is planning to provide bus service for a number of South Pacific island nations. Each nation consists of a collection of islands, some of which are connected by bridges. To save costs, the company wants to use the fewest number of buses possible. Every island must have access to a bus, but the company will only use one bus for any group of two or more islands that is connected by bridges.

Your job is to write a program which, given a map of the island nation, computes the number of islands, bridges, and the smallest number of buses needed for that country.

Input data

Input contains a sequence of maps, each given as a rectangular array of characters (at most 80 by 80). There is one blank line between each pair of maps. Input ends at end of file.

All maps contain only the characters dot (.), X, #, and B. Dots represent ocean water. X's and #'s represent island land. B's represents bridges, and each X represents the land that is the endpoint of one or more bridges.

Each map contains 1 or more rectangular islands. Different islands are not adjacent vertically or horizontally. Diagonal adjacency is not enough to drive a bus across.

Each map contains 0 or more horizontal or vertical bridges. Each bridge has at least one B, and connects only the two islands at its two endpoints. Bridges do not cross each other or extend over the # land of an island. No B may be adjacent to another B or X unless they are part of the same bridge.

Output data

For each map you should print the map number, followed by lines giving the number of islands, bridges, and buses needed. Print a blank line between each pair of map outputs. Follow the format of the sample output.

Examples

Input example #1
....................
....................
.....###............
.....##XBBBBX.......
.....###............
....................
.............###....
....####............
....####............
....###XBBBBX.......
.......B....#.......
.......B....#.......
.......B....X.##....
.......B....B.##....
...####X####X#......
...###########......
...###########......
...###########......
...###########......
....................

....######X###......##X##.......
..........B...........B.........
.........#X###########X###......

.......
.#.....
..#....
....##.
....##.
.......
.##....
...#...
.....#.

....##...
....##...
.#XBBBBX#
.##....##
Output example #1
Map 1
islands: 7
bridges: 4
buses needed: 4

Map 2
islands: 3
bridges: 2
buses needed: 1

Map 3
islands: 6
bridges: 0
buses needed: 6

Map 4
islands: 3
bridges: 1
buses needed: 2
Source 2013 ACM-ICPC North American Qualification Contest