题目背景

题目来源：https://hsin.hr/hio2024/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

经过在派对中成功的职业生涯后（我们不会透露这个派对的名字），Pero 在旅游局找到了一份工作。他监管着一个由 $N$ 个城市组成的网络，这些城市从 $1$ 到 $N$ 进行编号，每对城市之间都有一条单向道路相连。为了增加收入，他决定引入交通许可。Pero 原本希望为每条道路都引入一种特殊的许可，但这会引起上级的注意。因此，他决定引入 $K$ 种不同的许可，从 $1$ 到 $K$ 进行编号，并规定每条道路上行驶都需要持有特定的许可。

为了确保可观的收入，Pero 将满足以下属性：

• 对于每个城市 $v$，都存在一个城市 $u$，使得无法仅凭一种许可从城市 $v$ 行驶到城市 $u$。

Pero 请求你的帮助来确定最小的 $K$ 值，如果存在满足上述属性的许可分配方案，则输出这个 $K$ 值以及许可分配方案。如果不存在这样的分配方案，则输出 $-1$。

输入格式

第一行包含一个正整数 $N$。

接下来的 $N$ 行中，第 $i$ 行包含 $N$ 个数字 $a_{i,j}$，其中如果有一条从城市 $i$ 到城市 $j$ 的道路，则 $a_{i,j} = 1$。注意 $a_{i,i} = 0$，且对于 $i \neq j$，$a_{i,j}$ 和 $a_{j,i}$ 中只有一个非零。

输出格式

如果不存在满足属性的分配方案，则在第一行且仅第一行输出 $-1$。

否则，在第一行输出最小的正整数 $K$。

在接下来的 $N$ 行中，输出分配方案的描述。第 $i$ 行输出 $N$ 个数字 $b_{i,j}$，如果 $a_{i,j} = 0$，则 $b_{i,j} = 0$；否则，$1 \leq b_{i,j} \leq K$，表示在该道路上行驶需要哪种许可。

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

提示

【样例解释】

对于样例 $3$：需要第一个许可证的道路用红色标记，第二个许可证用蓝色，第三个许可证用绿色。从城市 $1$ 出发，仅使用一个许可证无法到达城市 $3$。从城市 $2$ 出发，仅使用一个许可证无法到达城市 $1$。从城市 $3$ 出发，仅使用一个许可证无法到达城市 $2$。从城市 $4$ 出发，仅使用一个许可证无法到达城市 $1$。

【数据范围】

在所有子任务中，$2 \leq N \leq 1000$。在每个子任务中， $15\%$ 的分数仅用于判断是否存在这样的分配方案。对于这些分数，如果你不输出 $-1$，你需要输出某个分配方案，但它不必满足 Pero 所期望的属性。

• 子任务 1（20 分）：$N\leq 5$；
• 子任务 2（80 分）：无其他约束限制。