Count the Number of Islands

You are given a two-dimensional grid of size m × n consisting of characters '1' (land) and '0' (water). An island is defined as a group of adjacent lands connected horizontally or vertically. Your task is to determine the number of distinct islands in the grid.

Formally, let the grid be defined as \( G \) where \( G[i][j] \) is either '1' or '0'. Two cells \( G[i][j] \) and \( G[k][l] \) belong to the same island if they are both '1' and there is a path connecting them, moving only in the four cardinal directions (up, down, left, right).

Input/Output Requirements: Your solution must read input from stdin and output the result to stdout.

inputFormat

The first line of input contains two integers m and n separated by a space, representing the number of rows and columns of the grid, respectively.

This is followed by m lines, each containing n space-separated characters (each either '0' or '1') representing the grid cells.

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 representing the number of islands in the grid.

Example: For the sample input above, the output should be 3.

## sample

1 1
1

1