Access Levels
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2400
Tags: bitmasks, dsu, flows, graph matchings

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?

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
3 2
01
11
10

Example output:
2
1 2 
2 2 
1 2 
2 2 
2 1

Example input:
2 3
101
100

Example output:
1
1 1 1
1 10 5
8
3

Editorial:
Suppose two documents $$$i$$$ and $$$j$$$ belong to the same access group, and the access level for the document $$$i$$$ is greater than the access level for document $$$j$$$. Then, every developer which has the access to the document $$$i$$$, has the access to the document $$$j$$$ as well; so, for every $$$d \in [1, n]$$$, the condition $$$a_{d,i} \le a_{d,j}$$$ must hold.
We can build a directed graph where the arc $$$i \rightarrow j$$$ represents that this condition holds for the (ordered) pair of documents $$$(i, j)$$$. Every access group should be a path in this graph — so, our problem now requires us to cover a directed graph with the minimum number of vertex-disjoint paths.
Let's assume that the graph is acyclic. Then every path is acyclic as well, so the number of vertices in a path is equal to the number of arcs in a path, plus one. Let $$$k$$$ be the number of paths, $$$v$$$ be the number of vertices, and $$$e$$$ be the total number of arcs used in the paths. It's easy to see that $$$k + e = v$$$; so, by maximizing the total number of arcs in the paths, we minimize the number of paths.
So, we need to choose the maximum number of arcs so that each vertex belongs to only one path among those formed by these arcs. It is equivalent to the combination of the following two conditions:
• each vertex should have at most one incoming chosen arc;
• each vertex should have at most one outgoing chosen arc.
Now our problem can be solved with network flows or bipartite matching. For example, one of the solutions is to create a bipartite graph where each vertex of the original graph is represented by two vertices, one for each part; and an arc $$$i \rightarrow j$$$ from the original graph is converted to the edge connecting the vertex $$$i$$$ in the left part and the vertex $$$j$$$ in the right part. It's easy to see that every matching in this graph fulfills the aforementioned two conditions, thus giving us a correct decomposition of an acyclic directed graph into vertex-disjoint paths — so, in order to minimize the number of such paths, we need to find the maximum matching. All that's left is to actually find these paths and convert them into the access groups/levels for the documents, and set access levels for the developers, which is pretty easy and straightforward to implement.
But wait, what if the graph is not acyclic? Fortunately, a cycle can exist only between two documents with identical access requirements. We can deal with these in one of two ways:
• compress all identical documents into one vertex;
• or use the document index as the tiebreak if two documents are completely identical otherwise.
Even the most basic implementation of bipartite matching with Kuhn's algorithm will yield a solution in $$$O(m^3 + m^2n)$$$.