Description

In image matching, one approach is to use edge information in the image and compute representative structural features for each piece of edge information to judge whether two images are similar. The Water-filling method starts from one endpoint of each edge component, walks along connected edge points, and numbers them in order. If, at some step, there is more than one different next connection point, the process splits into different paths and continues simultaneously until there are no connection points left. Two points are considered connected if they are adjacent up, down, left, or right.

For example, in the image of Figure $1$, there are three edge components, each composed of mutually connected edge points. Black squares represent edge points and white squares represent the background. In the Water-filling method, first, starting from the first row, scanning left to right and top to bottom, find the first black point and label it $1$. Next, find the next unnumbered connection point of $1$ and label it $2$. Continue to the next point and number sequentially. After point $6$, there are two unnumbered connection points; at this moment, split into two routes and number both as $7$, then continue. When there are no connected points left, end the numbering of the current edge component and continue numbering the other edge components in the image. The numbering obtained after traversing all edge components in Figure $1$ is shown in Figure $2$. Therefore, the numbers of steps required to complete these three edge components are $12$, $7$, and $3$; thus, $12$, $7$, and $3$ can serve as structural features representing this image. Note: Two points on a diagonal are not considered connected, as shown below.

Please write a program that, for each image, applies the Water-filling method to traverse all edge components and lists the number of steps needed for each edge component in the visitation order.

Input Format

The input contains one or more square images. Each image begins with its width $n$ $(1 \le n \le 1000)$. The next $n$ lines describe the image: $0$ denotes a white background point, and $1$ denotes a black edge point. Input ends at EOF.

Output Format

For each input image, after applying the Water-filling method to traverse all edge components, first print how many edge components the image contains. Then list the number of steps required for each edge component in the visitation order.

10 
0000000000 
0011110000 
0000010000 
0011111000 
0010110100 
0010010110 
0011110010 
0100010010 
0100000110 
0100000000 

3 
3 
7 
12

Hint

Translated by ChatGPT 5