在经历了一段我们不便透露的职业生涯后，Pero 在旅游部找到了一份工作。Pero 负责监管一个由 $N$ 个城市组成的网络，城市编号从 $1$ 到 $N$，每两个城市之间都恰好有一条单向道路。为了增加收入，他决定引入通行证制度。Pero 本想为每条道路都引入一种特殊的通行证，但这会引起上级的警觉。因此，他将引入 $K$ 种不同的通行证，编号从 $1$ 到 $K$，每条道路的通行都需要持有特定的通行证。

为了确保仍能获得可观的收入，Pero 满足于以下性质：

• 对于每个城市 $v$，都存在某个城市 $u$，使得无法仅凭一种通行证从城市 $v$ 到达城市 $u$。

Pero 请求你帮助他确定最小的 $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 \le b_{i,j} \le K$，表示通过该道路所需的通行证编号。

数据范围

在所有子任务中，$2 \le N \le 1000$。在每个子任务中，15% 的分数仅取决于判断是否存在这样的分配方案。对于这部分分数，如果你不输出 -1，则需要输出某种分配方案，但不一定要满足 Pero 所要求的性质。

样例

样例输入 1

3
0 1 0
0 0 1
1 0 0

样例输出 1

3
0 1 0
0 0 2
3 0 0

样例输入 2

3
0 1 1
0 0 1
0 0 0

样例输出 2

-1

样例输入 3

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

样例输出 3

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。