[AdditionalFile5512.zip](file://AdditionalFile5512.zip?type=additional_file)

#5512. 「COI 2024」Ministarstvo

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 COI 2024 T3「Ministarstvo」

在某个我们不便透露名称的政党中成功任职后，佩罗在旅游部找到了一份工作。佩罗负责监管一个由 $N$ 个城市组成的网络，这些城市用 $1$ 到 $N$ 的数字编号，任意两个城市之间都恰好有一条单向道路。为了增加收入，他决定引入交通许可证。佩罗本想为每条道路都设置一种特殊的许可证，但这会惊动他的上级。因此，他将引入 $K$ 种不同的许可证，用 $1$ 到 $K$ 编号，并且每条道路都需要持有特定的许可证才能通行。

为了仍然确保可观的收入，佩罗将满足于以下性质：

• 对于每个城市 $v$，都存在某个城市 $u$，使得无法仅使用一种许可证从城市 $v$ 前往城市 $u$。

佩罗请求你的帮助，以确定满足所需性质的最小 $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$，表示在该条道路上行驶需要哪种许可证。

样例 1

输入

3
0 1 0
0 0 1
1 0 0

输出

3
0 1 0
0 0 2
3 0 0

样例 2

输入

3
0 1 1
0 0 1
0 0 0

输出

-1

样例 3

输入

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

需要第一种许可证的道路用红色标记，第二种用蓝色，第三种用绿色。

• 从城市 $1$，无法仅使用一种许可证到达城市 $3$。
• 从城市 $2$，无法仅使用一种许可证到达城市 $1$。
• 从城市 $3$，无法仅使用一种许可证到达城市 $2$。
• 从城市 $4$，无法仅使用一种许可证到达城市 $1$。

数据范围与提示

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

详细子任务附加限制及分值如下表所示：