P10751 [COI 2024] Ministarstvo (Call for checker).

Source: . The translation is from [Wenxin Yiyan](https://yiyan.baidu.com/). If you have a better translation, please provide it in the discussion area.

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$.

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.

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.

**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