CF1765A.Access Levels

BerSoft is the biggest IT corporation in Berland, and Monocarp is the head of its security department. This time, he faced the most difficult task ever.

Basically, there are $n$ developers working at BerSoft, numbered from $1$ to $n$. There are $m$ documents shared on the internal network, numbered from $1$ to $m$. There is a table of access requirements $a$ such that $a_{i,j}$ (the $j$-th element of the $i$-th row) is $1$ if the $i$-th developer should have access to the $j$-th document, and $0$ if they should have no access to it.

In order to restrict the access, Monocarp is going to perform the following actions:

• choose the number of access groups $k \ge 1$;
• assign each document an access group (an integer from $1$ to $k$) and the required access level (an integer from $1$ to $10^9$);
• assign each developer $k$ integer values (from $1$ to $10^9$) — their access levels for each of the access groups.

The developer $i$ has access to the document $j$ if their access level for the access group of the document is greater than or equal to the required access level of the document.

What's the smallest number of access groups Monocarp can choose so that it's possible to assign access groups and access levels in order to satisfy the table of access requirements?

BerSoft 是 Berland 国内规模最大的 IT 公司，而 Monocarp 是其安全部门的负责人。这一次，他面临了有史以来最困难的任务。

简而言之，BerSoft 共有 $n$ 名开发者，编号为 $1$ 至 $n$；公司内部网络上共享着 $m$ 份文档，编号为 $1$ 至 $m$。存在一张访问权限需求表 $a$，其中 $a_{i,j}$（即第 $i$ 行的第 $j$ 个元素）为 $1$ 表示第 $i$ 名开发者应当拥有对第 $j$ 份文档的访问权限，为 $0$ 则表示不应拥有该文档的访问权限。

为了限制访问权限，Monocarp 将执行以下操作：

• 选定访问组的数量 $k \ge 1$；
• 为每份文档分配一个访问组（取值为 $1$ 至 $k$ 的整数）以及一个所需的访问等级（取值为 $1$ 至 $10^9$ 的整数）；
• 为每位开发者分配 $k$ 个整数值（取值均为 $1$ 至 $10^9$），分别表示其在各个访问组中的访问等级。

当且仅当开发者 $i$ 在文档 $j$ 所属访问组中的访问等级 大于等于 文档 $j$ 所需的访问等级时，开发者 $i$ 才能访问文档 $j$。

问：Monocarp 能选择的最小访问组数量 $k$ 是多少，使得存在一种访问组与访问等级的分配方案，能够完全满足上述访问权限需求表？

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 500$) — the number of developers and the number of documents.

Each of the next $n$ lines contains a binary string of length $m$ — the table of access requirements. The $j$-th element of the $i$-th row is $1$ if the $i$-th developer should have access to the $j$-th document, and $0$ if they should have no access to it.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 500$）—— 分别表示开发人员数量和文档数量。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，表示访问权限要求表。第 $i$ 行的第 $j$ 个元素为 $1$ 表示第 $i$ 位开发人员应有权访问第 $j$ 个文档；为 $0$ 则表示其不应拥有对该文档的访问权限。

The first line should contain a single integer $k$ — the smallest number of access groups Monocarp can choose so that it's possible to assign access groups and access levels in order to satisfy the table of access requirements.

The second line should contain $m$ integers from $1$ to $k$ — the access groups of the documents.

The third line should contain $m$ integers from $1$ to $10^9$ — the required access levels of the documents.

The $i$-th of the next $n$ lines should contain $k$ integers from $1$ to $10^9$ — the access level of the $i$-th developer on each of the access groups.

If there are multiple solutions, print any of them.

第一行应包含一个整数 $k$ —— Monocarp 能选择的最小访问组数量，使得存在一种方式为文档分配访问组和访问级别，从而满足访问需求表。

第二行应包含 $m$ 个介于 $1$ 到 $k$ 之间的整数 —— 各文档所属的访问组。

第三行应包含 $m$ 个介于 $1$ 到 $10^9$ 之间的整数 —— 各文档所需的访问级别。

接下来的 $n$ 行中，第 $i$ 行应包含 $k$ 个介于 $1$ 到 $10^9$ 之间的整数 —— 第 $i$ 位开发者在各访问组上的访问级别。

若存在多种解法，输出任意一种即可。

In the first example, we assign the documents to different access groups. Both documents have level $2$ in their access group. This way, we can assign the developers, who need the access, level $2$, and the developers, who have to have no access, level $1$.

If they had the same access group, it would be impossible to assign access levels to developers $1$ and $3$. Developer $1$ should've had a lower level than developer $3$ in this group to not be able to access document $1$. At the same time, developer $3$ should've had a lower level than developer $1$ in this group to not be able to access document $2$. Since they can't both have lower level than each other, it's impossible to have only one access group.

In the second example, it's possible to assign all documents to the same access group.

在第一个例子中，我们将文档分配给不同的访问组。两个文档在其所属的访问组中均具有等级 $2$。这样，我们可以为需要访问权限的开发人员分配等级 $2$，而为必须禁止访问的开发人员分配等级 $1$。

如果它们属于同一访问组，则无法为开发人员 $1$ 和开发人员 $3$ 分配合适的访问等级：

• 开发人员 $1$ 在该组中的等级需低于开发人员 $3$，才能无法访问文档 $1$；
• 同时，开发人员 $3$ 在该组中的等级又需低于开发人员 $1$，才能无法访问文档 $2$。
  由于二者不可能互为更低等级，因此仅使用一个访问组是不可能实现的。

在第二个例子中，可以将所有文档分配到同一个访问组。