P10751 [COI 2024] Ministarstvo（征集 checker）

题目来源：。翻译来自 [文心一言](https://yiyan.baidu.com/)。如果有更好的翻译请在讨论区提供。

经过在派对中成功的职业生涯后（我们不会透露这个派对的名字），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$：需要第一个许可证的道路用红色标记，第二个许可证用蓝色，第三个许可证用绿色。从城市 $1$ 出发，仅使用一个许可证无法到达城市 $3$。从城市 $2$ 出发，仅使用一个许可证无法到达城市 $1$。从城市 $3$ 出发，仅使用一个许可证无法到达城市 $2$。从城市 $4$ 出发，仅使用一个许可证无法到达城市 $1$。  **【数据范围】** 在所有子任务中，$2 \leq N \leq 1000$。在每个子任务中， $15\%$ 的分数仅用于判断是否存在这样的分配方案。对于这些分数，如果你不输出 $-1$，你需要输出某个分配方案，但它不必满足 Pero 所期望的属性。 - 子任务 1（20 分）：$N\leq 5$； - 子任务 2（80 分）：无其他约束限制。