Count Distinct Islands

You are given a 2D grid of size \(m \times n\) consisting of 0s and 1s. Each cell containing a 1 represents land and a cell containing a 0 represents water. An island is formed by connecting adjacent lands horizontally or vertically. Your task is to find and print the number of distinct islands (i.e. connected components) in the grid.

Note: Two cells are considered adjacent if they share a side. Diagonally adjacent cells are not connected.

Example:

Input:
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Output:
3

</p>

The above grid contains 3 islands.

inputFormat

The input is given via stdin and has the following format:

• The first line contains two integers \(m\) and \(n\) representing the number of rows and columns respectively.
• The next \(m\) lines each contain \(n\) integers (either 0 or 1) separated by spaces, representing each row of the grid.

You can assume that \(1 \leq m, n \leq 1000\).

outputFormat

Output a single integer to stdout representing the number of islands present 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