Black Regions

Problem Description

You are given an $n \times m$ grid. Some cells are painted black (marked 1) and the rest are white (marked 0). Count the number of 4-connected black components. A 4-connected black component is a region of black cells in which every black cell can reach every other black cell using only black cells and only up/down/left/right moves.

Input Format

The first line contains two integers $n, m$ ($1 \le n, m \le 100$): the size of the grid.

The next $n$ lines each contain $m$ integers, each 0 or 1, telling whether the cell is black or white.

Output Format

One integer: the number $ans$ of black components.

Sample Input

3 3
111
010
101

Sample Output

3

Limitation

1 s, 1024 KiB for each test case.