{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBerSoft 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. \u003c/p\u003e\u003cp\u003eBasically, 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.\u003c/p\u003e\u003cp\u003eIn order to restrict the access, Monocarp is going to perform the following actions: \u003c/p\u003e\u003cul\u003e \u003cli\u003e choose the number of access groups $$$k \\ge 1$$$; \u003c/li\u003e\u003cli\u003e assign each document an access group (an integer from $$$1$$$ to $$$k$$$) and the required access level (an integer from $$$1$$$ to $$$10^9$$$); \u003c/li\u003e\u003cli\u003e assign each developer $$$k$$$ integer values (from $$$1$$$ to $$$10^9$$$)\u0026nbsp;— their access levels for each of the access groups. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eWhat\u0027s the smallest number of access groups Monocarp can choose so that it\u0027s possible to assign access groups and access levels in order to satisfy the table of access requirements?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\le n, m \\le 500$$$)\u0026nbsp;— the number of developers and the number of documents.\u003c/p\u003e\u003cp\u003eEach of the next $$$n$$$ lines contains a binary string of length $$$m$$$\u0026nbsp;— 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe first line should contain a single integer $$$k$$$\u0026nbsp;— the smallest number of access groups Monocarp can choose so that it\u0027s possible to assign access groups and access levels in order to satisfy the table of access requirements.\u003c/p\u003e\u003cp\u003eThe second line should contain $$$m$$$ integers from $$$1$$$ to $$$k$$$\u0026nbsp;— the access groups of the documents.\u003c/p\u003e\u003cp\u003eThe third line should contain $$$m$$$ integers from $$$1$$$ to $$$10^9$$$\u0026nbsp;— the required access levels of the documents.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$n$$$ lines should contain $$$k$$$ integers from $$$1$$$ to $$$10^9$$$\u0026nbsp;— the access level of the $$$i$$$-th developer on each of the access groups.\u003c/p\u003e\u003cp\u003eIf there are multiple solutions, print any of them.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n01\n11\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 2 \n2 2 \n1 2 \n2 2 \n2 1 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3\n101\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 1 1\n1 10 5\n8\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn 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$$$.\u003c/p\u003e\u003cp\u003eIf they had the same access group, it would be impossible to assign access levels to developers $$$1$$$ and $$$3$$$. Developer $$$1$$$ should\u0027ve 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\u0027ve had a lower level than developer $$$1$$$ in this group to not be able to access document $$$2$$$. Since they can\u0027t both have lower level than each other, it\u0027s impossible to have only one access group.\u003c/p\u003e\u003cp\u003eIn the second example, it\u0027s possible to assign all documents to the same access group. \u003c/p\u003e"}}]}