Counting Distinct Groups of Ones

You are given a binary matrix (a matrix consisting of 0s and 1s). A group is defined as a set of connected 1s, where connectivity is established horizontally or vertically (but not diagonally). Your task is to count the number of distinct groups in the matrix.

If the matrix is empty, output 0.

For example, consider the following 5x5 matrix:

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

This matrix contains 5 distinct groups of connected 1s.

The connectivity can be expressed using the following DFS-based algorithm:

For each cell in the matrix, if it contains a 1 and has not been visited, perform a DFS traversal to mark all cells in that connected group. Increment the group count accordingly.

The relation of connectivity can be defined mathematically as:

\( G = \{(i,j) \mid A[i][j] = 1 \}\) and two cells \((i,j)\) and \((k,l)\) belong to the same group if there exists a path \( (i,j) = (i_0,j_0), (i_1,j_1), \ldots, (i_m,j_m) = (k,l) \) such that for every \(0 \leq t

inputFormat

The input is read from stdin and is formatted as follows:

1. The first line contains an integer \(n\), the number of rows in the matrix. If \(n = 0\), the matrix is empty.
2. If \(n > 0\), the next \(n\) lines each contain space-separated integers (0 or 1) representing the rows of the matrix.

outputFormat

Output to stdout a single integer representing the number of distinct groups of connected 1s in the matrix.

## sample

5
1 1 0 0 0
0 1 0 0 1
1 0 0 1 1
0 0 0 0 0
1 1 0 1 1

5