Counting Islands in a 2D Grid

You are given a 2D grid of size \(n \times m\) where each cell contains either a 0 or a 1. A cell with a value of 1 represents land, and 0 represents water. An island is defined as a group of adjacent lands connected horizontally or vertically.

Your task is to count the total number of islands in the grid.

Note: Diagonal connections do not count. You should read the grid from standard input and output the number of islands to standard output.

For example, given the grid:

\[ \begin{matrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix} \]

The output should be 3.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of rows and columns of the grid, respectively. The following \(n\) lines each contain \(m\) integers separated by spaces representing the grid.

For example:

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

outputFormat

Output a single integer on a new line representing the number of islands found in the grid.

## sample

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

3