Access Levels

题意翻译

有 $n$ 个工作人员和 $m$ 个文件。 你需要将 $m$ 个文件分成 $k$ 组，令第 $i$ 个文件分第 $s_i$ 组。然后对第 $i$ 个文件需要定一个访问等级 $c_i$，满足 $c_i$ 为 $[1,10^9]$ 内的整数。 然后对于第 $i$ 个工作人员和第 $j$ 组文件需要定一个访问等级 $b_{i,j}$，满足 $b_{i,j}$ 为 $[1,10^9]$ 内的整数。 同时给出一个 $n\times m$ 的数组 $a$，$a_{i,j}=1$ 表示 $b_{i,s_j}\ge c_j$，$a_{i,j}=0$ 表示 $b_{i,s_j}<c_j$。 求 $k$ 的最小值，以及任意一组对应的合法 $s,c,b$。$n,m\le 500$。

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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.

**题意翻译**

有 $n$ 个工作人员和 $m$ 个文件。需要将 $m$ 个文件分成 $k$ 组，第 $i$ 个文件分到第 $s_i$ 组。每个文件需指定一个访问等级 $c_i$，满足 $c_i$ 为 $[1,10^9]$ 内的整数。对于每个工作人员和每个文件组，需指定一个访问等级 $b_{i,j}$，也在 $[1,10^9]$ 内。给定一个 $n\times m$ 的数组 $a$，$a_{i,j}=1$ 表示工作人员 $i$ 对文件组 $s_j$ 的访问等级 $b_{i,s_j}\ge c_j$，$a_{i,j}=0$ 表示 $b_{i,s_j}
**题目描述**

BerSoft 是 Berland 最大的 IT 公司，Monocarp 是其安全部门的负责人。基本任务如下：

- BerSoft 有 $n$ 名开发人员，编号从 $1$ 到 $n$。
- 共有 $m$ 个文档在网络内共享，编号从 $1$ 到 $m$。
- 存在一个访问要求表 $a$，其中 $a_{i,j}$ 为 $1$ 表示第 $i$ 个开发人员应访问第 $j$ 个文档，为 $0$ 则相反。

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

- 选择访问组数 $k \ge 1$；
- 为每个文档分配一个访问组（$1$ 到 $k$ 之间的整数）和所需的访问级别（$1$ 到 $10^9$ 之间的整数）；
- 为每个开发人员分配 $k$ 个整数（$1$ 到 $10^9$ 之间）——他们每个访问组的访问级别。

如果开发人员 $i$ 对文档 $j$ 的访问组级别大于或等于文档的所需访问级别，则该开发人员可以访问文档。

Monocarp 可以选择的最小的访问组数 $k$ 是多少，以便可以分配访问组和访问级别以满足访问要求表？

**输入输出格式**

**输入格式**

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

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

**输出格式**

第一行应包含一个整数 $k$——Monocarp 可以选择的最小的访问组数，以便可以分配访问组和访问级别以满足访问要求表。

第二行应包含 $m$ 个整数，范围从 $1$ 到 $k$——文档的访问组。

第三行应包含 $m$ 个整数，范围从 $1$ 到 $10^9$——文档的所需访问级别。

接下来的 $n$ 行，每行应包含 $k$ 个整数，范围从 $1$ 到 $10^9$——第 $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$。由于他们不能都比对方级别低，所以不可能只有一个访问组。

在第二个示例中，可以将所有文档分配到同一个访问组。**题意翻译** 有 $n$ 个工作人员和 $m$ 个文件。需要将 $m$ 个文件分成 $k$ 组，第 $i$ 个文件分到第 $s_i$ 组。每个文件需指定一个访问等级 $c_i$，满足 $c_i$ 为 $[1,10^9]$ 内的整数。对于每个工作人员和每个文件组，需指定一个访问等级 $b_{i,j}$，也在 $[1,10^9]$ 内。给定一个 $n\times m$ 的数组 $a$，$a_{i,j}=1$ 表示工作人员 $i$ 对文件组 $s_j$ 的访问等级 $b_{i,s_j}\ge c_j$，$a_{i,j}=0$ 表示 $b_{i,s_j}