Water-filling Edge Traversal Count

In image matching, one method is to use edge information from an image to compute a structured feature that represents the image. In this problem, an image is given as a grid of characters where a black cell (represented by '1') indicates an edge point and a white cell (represented by '0') indicates the background. Two cells are considered connected if they are adjacent vertically or horizontally (diagonal cells are not connected).

The edge points in the image form one or more edge graphs (connected components). The Water-filling method is defined as follows: traverse the grid in row-major order (from top to bottom and left to right) to find the first unvisited edge point. From this starting point, perform a multi-path traversal: assign the starting cell the number \(1\); then, from each current cell, move to any unvisited connected neighbor cell, assigning sequential numbers. If at any moment a cell has more than one unvisited connected neighbor, the traversal splits into different paths which continue concurrently with increasing numbering. When a path can no longer proceed (i.e. no unvisited adjacent cell), that edge graph’s traversal ends. The number of steps taken (which is equal to the number of cells in that connected component) is used as a representative structural feature for that edge graph.

Your task is: given an image, compute the water-filling traversal for each edge graph and list the number of steps (i.e. cells visited) for each edge graph in the order they are discovered.

For example, consider an image where there are three edge graphs, and the number of steps required to traverse them are \(12\), \(7\), and \(3\) respectively. Then the output should be:

12 7 3

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 1000\)), representing the number of rows and columns of the image.

Each of the following \(n\) lines contains a string of length \(m\) consisting only of the characters '0' and '1', where '1' represents an edge point and '0' represents the background.

outputFormat

Output a single line with the step counts (i.e. the number of cells in the edge graph) for each connected component (edge graph) in the order they are discovered, separated by a single space.

sample

3 3
101
010
101

1 1 1 1 1