Number of Distinct Islands

Given a 2D binary grid, your task is to count the number of distinct islands. An island is a group of connected 1's (land) connected horizontally or vertically. Two islands are considered the same if one can be translated (moved) to equal the other; rotations and reflections are not allowed.

For example, consider the following grid:

1 1 0 0 0
1 0 0 1 1
1 1 0 1 0
0 0 0 0 0
1 1 1 0 0

In this grid, there are 3 distinct islands. Write a program to compute the number of distinct islands.

inputFormat

The first line contains two integers n and m, separated by a space, representing the number of rows and columns in the grid, respectively. This is followed by n lines, each containing m integers (0 or 1) separated by spaces, indicating the grid.

outputFormat

Output a single integer which is the number of distinct islands in the grid.## sample

3 3
0 0 0
0 0 0
0 0 0

0