Painted Areas

Interview

Time limit2sMemory limit128 MB

Summary
Count connected components of 1-cells in a grid (4-directional adjacency) and output the count and the size of the largest component.
Level

Easy3 of 10

Topics
BFS, DFS, Matrix
Solved
No attempts yet

Problem

A large canvas is divided into cells. Each cell is either unpainted, represented by 0, or painted, represented by 1. Painted cells that are adjacent vertically or horizontally belong to the same picture. Cells that touch only diagonally are not connected.

Find the number of pictures on the canvas and the area of the largest picture. The area of a picture is the number of cells with value 1 in that picture.

Input

The first line contains the height n (1 <= n <= 500) and width m (1 <= m <= 500) of the canvas.

Each of the next n lines contains m integers, each either 0 or 1, separated by spaces. A 0 means an unpainted cell, and a 1 means a painted cell.

Output

Print the number of pictures on the first line.

Print the area of the largest picture on the second line. If there is no picture, print 0 on the second line.

Examples1

  1. Example 1

    Input
    6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1
    Expected output
    4
9