Background

Source: https://hsin.hr/hio2024/. The translation is from Wenxin Yiyan. If you have a better translation, please provide it in the discussion area.

Problem Description

After a successful career at a party (we will not reveal the party’s name), Pero found a job at the tourism board. He supervises a network of $N$ cities, numbered from $1$ to $N$, where for every pair of cities there is a one-way road connecting them. To increase revenue, he decided to introduce travel permits. Pero originally wanted to introduce a special permit for every road, but that would attract the attention of his superiors. Therefore, he decided to introduce $K$ different permits, numbered from $1$ to $K$, and require that traveling on each road needs a specific permit.

To ensure considerable revenue, Pero wants the following property to hold:

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

Pero asks for your help to determine the minimum value of $K$. If there exists a permit assignment that satisfies the property above, output this $K$ and such an assignment. If no such assignment exists, output $-1$.

Input Format

The first line contains a positive integer $N$.

In the next $N$ lines, the $i$-th line contains $N$ numbers $a_{i,j}$, where if there is a road from city $i$ to city $j$, then $a_{i,j} = 1$. Note that $a_{i,i} = 0$, and for $i \neq j$, exactly one of $a_{i,j}$ and $a_{j,i}$ is non-zero.

Output Format

If there is no assignment satisfying the property, output $-1$ on the first line, and only on the first line.

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

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

3
0 1 0
0 0 1
1 0 0

3
0 1 0
0 0 2
3 0 0

3
0 1 1
0 0 1
0 0 0

-1

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

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

Hint

Sample Explanation

For sample $3$: roads that require 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.

Constraints

In all subtasks, $2 \leq N \leq 1000$. In each subtask, $15\%$ of the points are only for deciding whether such an assignment exists. For these points, if you do not output $-1$, you need to output some assignment, but it does not have to satisfy the property Pero wants.

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

Translated by ChatGPT 5