Problem Background

Problem Source: https://hsin.hr/hio2024/. Translation provided by ERNIE Bot. If you have a better translation, please provide it in the discussion section.

Problem Description

After a successful career at a party (whose name we won't disclose), Pero has found a job at the tourism bureau. He oversees a network of $N$ cities, numbered from $1$ to $N$, with each pair of cities connected by a one-way road. To increase revenue, he decides to introduce traffic permits. Pero initially wanted to introduce a special permit for each road, but this would draw attention from higher-ups. Therefore, he decides to introduce $K$ different permits, numbered from $1$ to $K$, and stipulates that each road requires a specific permit to travel on.

To ensure substantial income, Pero will satisfy the following property:

• For each city $v$, there exists a city $u$ such that it is impossible to travel from city $v$ to city $u$ using only one permit.

Pero requests your help to determine the minimum $K$ value. If there exists a permit allocation scheme that satisfies the above property, output this $K$ value along with the allocation scheme. If no such scheme exists, output $-1$.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain $N$ digits $a_{i,j}$, where $a_{i,j} = 1$ if there is a road from city $i$ to city $j$. Note that $a_{i,i} = 0$, and for $i \neq j$, only one of $a_{i,j}$ or $a_{j,i}$ is non-zero.

Output Format

If no allocation scheme satisfying the property exists, output $-1$ on the first line and only the first line.

Otherwise, on the first line output the minimum positive integer $K$.

In the next $N$ lines, output the description of the allocation scheme. The $i$-th line should contain $N$ digits $b_{i,j}$, where if $a_{i,j} = 0$, then $b_{i,j} = 0$; otherwise, $1 \leq b_{i,j} \leq K$, indicating which permit is required to travel on that road.

Sample Input and Output

Sample Input #1

3
0 1 0
0 0 1
1 0 0

Sample Output #1

3
0 1 0
0 0 2
3 0 0

Sample Input #2

3
0 1 1
0 0 1
0 0 0

Sample Output #2

-1

Sample Input #3

4
0 1 0 1
0 0 1 1
1 0 0 0
0 0 1 0

Sample Output #3

3
0 1 0 1
0 0 2 3
3 0 0 0
0 0 2 0

Notes

[Sample Explanation]

For Sample 3: Roads requiring the first permit are marked in red, the second permit in blue, and the third permit in green. Starting from city 1, it is impossible to reach city 3 using only one permit. Starting from city 2, it is impossible to reach city 1 using only one permit. Starting from city 3, it is impossible to reach city 2 using only one permit. Starting from city 4, it is impossible to reach city 1 using only one permit.

[Data Range]

In all subtasks, $2 \leq N \leq 1000$. In each subtask, $15\%$ of the score is for determining whether such an allocation scheme exists. For these scores, if you do not output $-1$, you need to output an allocation scheme, but it does not have to satisfy Pero's desired property.

• Subtask 1 (20 points): $N \leq 5$;
• Subtask 2 (80 points): No additional constraints.

见题面 Input 部分

见题面 Output 部分