BerSoft 是 Berland 最大的 IT 公司,Monocarp 是其安全部门的负责人。这一次,他面临着有史以来最艰巨的任务。
基本上,有 $$$n$$$ 开发人员在 BerSoft 工作,编号从 $$$1$$$ 到 $$$n$$$。内网共享了$$$m$$$个文档,编号从$$$1$$$到$$$m$$$。有一个访问要求表$$$a$$$,如果第$$$i$$$个开发人员应该有权访问第$$$j$$$个文档,则$$$a_{i,j}$$$(第$$$i$$$行的第$$$j$$$个元素)为$$$1$$$,如果他们无权访问该文档,则为$$$0$$$。
为了限制访问,Monocarp 将执行以下操作:
- 选择访问组的数量 $$$k \ge 1$$$;
- 为每个文档分配一个访问组(从 $$$1$$$ 到 $$$k$$$ 的整数)和所需的访问级别(从 $$$1$$$ 到 $$$10^9$$$ 的整数);
- 为每个开发人员分配 $$$k$$$ 整数值(从 $$$1$$$ 到 $$$10^9$$$)——每个访问组的访问级别。
如果开发人员 $$$i$$$ 对文档访问组的访问级别大于或等于文档所需的访问级别,则他们有权访问文档 $$$j$$$。
Monocarp 可以选择的最小访问组数是多少,以便可以分配访问组和访问级别以满足访问要求表?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 500$$$) — 开发者数量和文档数量。
接下来的 $$$n$$$ 行均包含长度为 $$$m$$$ 的二进制字符串 — 访问要求表。如果第 $$$i$$$ 个开发人员应该有权访问第 $$$j$$$ 个文档,则第 $$$i$$$ 行的第 $$$j$$$ 个元素为 $$$1$$$;如果他们无权访问该文档,则第 $$$j$$$ 个元素为 $$$0$$$。
输出
第一行应包含一个整数 $$$k$$$ — Monocarp 可以选择的最小访问组数,以便可以分配访问组和访问级别以满足访问要求表。
第二行应包含从 $$$1$$$ 到 $$$k$$$ 的 $$$m$$$ 整数 - 文档的访问组。
第三行应包含从 $$$1$$$ 到 $$$10^9$$$ 的 $$$m$$$ 整数 - 文档所需的访问级别。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行应包含从 $$$1$$$ 到 $$$10^9$$$ 的 $$$k$$$ 整数 - 每个访问组中第 $$$i$$$ 开发人员的访问级别。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
3 2 01 11 10
输出 #1
2 1 2 2 2 1 2 2 2 2 1
输入 #2
2 3 101 100
输出 #2
1 1 1 1 1 10 5 8 3
注意
在第一个示例中,我们将文档分配给不同的访问组。两个文档的访问组中的级别均为 $$$2$$$。这样,我们可以为需要访问权限的开发人员分配级别 $$$2$$$,为不需要访问权限的开发人员分配级别 $$$1$$$。
如果他们具有相同的访问组,则无法为开发人员 $$$1$$$ 和 $$$3$$$ 分配访问级别。该组中开发人员 $$$1$$$ 的级别应该低于开发人员 $$$3$$$,因此无法访问文档 $$$1$$$。同时,该组中开发人员$$$3$$$ 的级别应低于开发人员$$$1$$$,因此无法访问文档$$$2$$$。由于它们的级别不能都低于对方,因此不可能只有一个访问组。
在第二个示例中,可以将所有文档分配到同一访问组。