Background

One set of testdata is hand-made. Hacks are welcome.

Problem Description

Jimmy and Symbol agreed to watch the stars together. The vast starry sky can be seen as a matrix with length $N$ and width $M$. There are $N \times M$ positions in the matrix. A position can be represented by coordinates $(i,j)$ ($1 \le i \le N$, $1 \le j \le M$). Each position may be empty, or may contain a star.

For a position $(i,j)$, the adjacent positions are the 8 positions: left, upper-left, up, upper-right, right, lower-right, down, and lower-left. Stars on adjacent positions are considered to belong to the same constellation. This relationship is transitive. For example, if positions $(1,1)$, $(1,2)$, and $(1,3)$ all contain stars, then these three stars are considered to be in the same constellation. Constellations with the same number of stars are considered to be in the same galaxy (constellations in the same galaxy do not have to be adjacent). The size of a galaxy is the total number of stars contained in that galaxy.

Since Symbol likes galaxies very much, he wants to test Jimmy by asking him to find how many galaxies there are in the starry sky, and also how large the largest galaxy is.

Input Format

The first line contains two integers $N, M$ representing the length and width of the matrix.

Next, there are $N$ lines, each containing $M$ characters. Each character is either . or *. In these $N$ lines, the $j$-th character of the $i$-th line is * if there is a star at position $(i,j)$; otherwise, it is empty.

Output Format

Output a single line with two integers, separated by a space, representing the number of galaxies and the size of the largest galaxy, respectively.

5 7
*......
..**..*
.*...*.
...*...
....*..

3 4

10 10
**..**.**.
***....*..
*...**.**.
...*..*...
..........
**...**.*.
..*.*....*
..........
***..*.*..
.***..*...

4 12

Hint

For $20\%$ of the testdata, $N, M \le 20$, and the maximum galaxy size does not exceed 200.

For $50\%$ of the testdata, $N, M \le 400$.

For $70\%$ of the testdata, $N, M \le 1100$.

For $100\%$ of the testdata, $2 \le N, M \le 1500$, and the maximum galaxy size does not exceed 100000.

Translated by ChatGPT 5