URI Online Judge | 2477

Distribution Network

By Lucas Bucior, URI Online Judge BR Brazil

Timelimit: 1

Christmas is coming and many people have not yet festooned their homes, chancellor Jack Redd is distributing red lights to host cities. As are many lights to distribute, Jack handed you a map, which contains information about the city, the central unit, its decoration points and the streets. Look at the image.

In the picture, the central unit receives the lights and sends them to the decoration points 1, 2, 3 and 4, respectively. Each decorating point needs a certain amount of lights that is measured by the size of the grouping of points (. ) times the minimum distance of this grouping to the central unit. It is possible to walk by a decoration point if it is bigger than 1 and if by chance the wires can not arrive at a decoration point, the city will not be part of the Christmas show anymore.

A decorative point is formed by a group of ( . ). It is necessary to arrive with the threads in all the decorative points, so that the party is big and beautiful. A decorative dot can pass wires to its adjacent ones.

The central unit consists of the largest grouping of ( . ) on the map. JJack revealed it just for you, for security reasons. Since the wires are already part of the central unit, pay attention to which parts even need wires, precisely where it has ( +) or its decorative points.The wires can be routed to the four directions (North, South, East and West). Can you distribute the lights to the party?

Input

The entry consists of multiple instances. The first line of each instance contains two integers N e M (1 ≤ N, M ≤ 103), which correspond to the number of rows and columns on the map delivered by Jack. The N lines below contain M characters, defined as ( . ), ( + ) ou ( # ), representing the central unit and its decoration points, a valid point to be explored and a barrier which prevents the passage of the wires respectively.The entry ends with end-of-file (EOF).

Output

For each instance, your program should print the message "Instance #H:" where H is the instance number, sequential and increasing (from 01 to 99). Then print out the size of the central unit, the minimum path to arrive at all the decoration points and how many lights the city needs. If the wires can not reach all decoration points, your program should print the "Network Error" message.

Your program should print a blank line between two consecutive instances.

Input Sample Output Sample

7 7
. . + # + . .
. + + # + + .
+ + + . + + +
# # . . . # #
+ + + . + + +
. + + # + + .
. . + # + . .
10 10
. . . . . . . . . .
+ + + + + + + + + +
. . # # # # # # # #
+ + + + + + + + + +
# # # # # # # # . .
+ + + + + + + + + +
. . # # # # # # # #
+ + + + + + + + + +
# # # # # # # # . .
. . . . + + + + + +

Instance #01:
5 12 36

Instance #02:
10 92 252