Blots on Paper
Blots on Paper
Some ink was spilled on a grid paper measuring M×N cells. Each cell of the paper is now considered either pained or clean. Two painted cells belong to the same blot if there is a path from one of the cells to the other that goes through painted cells only and on each step moves from one cell to another only horizontally or vertically.
Count the number of blots and the area of the largest blot (that is, the number of cells it consists of).
Input data
The first input line contains the integers M and N (1 ≤ M, N ≤ 10^5, 1 < M·N ≤ 10^6). Each of the following M lines consists of N characters 0 or 1, where 0 denotes a clean and 1 a painted cell. There is at least one painted cell.
Output data
The only output line should contain two integers: the number of blots and the area of the largest blot.
Examples
6 7 1001001 1111011 1001000 1001111 0100000 0000000
3 13