Slash Maze

Interview

Time limit1sMemory limit128 MB

Summary

Count the closed loops in a grid of slash and backslash walls and report the longest loop's length, where each cell splits into two triangles.

Level: Medium7 of 10
Topics: Graph, DFS, Matrix, Implementation
Solved: No attempts yet

Problem

By filling the cells of a rectangle with slashes (/) and backslashes (\), you can generate small mazes. Each cell contains exactly one slash or backslash, which acts as a wall that splits the cell into two triangular halves.

Paths in such a maze never branch, so the maze consists only of closed loops (cycles) and open paths that enter at one border and leave at another. We are interested only in the closed loops.

Your task is to count the cycles and to determine the length of the longest one. The length of a cycle is the number of small triangular pieces it is made of; each grid square is split by its slash into two such triangles. For example, in the first sample maze there are two cycles: the longer one has length 16 and the shorter one has length 4.

Input

The input contains several maze descriptions. Each description begins with one line containing two integers $w$ and $h$ ( $1 \le w, h \le 75$ ), the width and the height of the maze. The next $h$ lines represent the maze and contain exactly $w$ characters each; every character is either / or \.

The input is terminated by a line with $w = h = 0$ ; this final case must not be processed.

Output

For each maze, first print a line Maze #n:, where $n$ is the number of the maze (starting from 1). Then print a line k Cycles; the longest has length l., where $k$ is the number of cycles and $l$ is the length of the longest cycle. If the maze contains no cycle, print There are no cycles. instead. Separate the outputs of consecutive mazes with a blank line.

Examples1

Example 1

Input

6 4
\//\\/
\///\/
//\\/\
\/\///
3 3
///
\//
\\\
0 0

Expected output

Maze #1:
2 Cycles; the longest has length 16.

Maze #2:
There are no cycles.