Monochromatic Path Blockage in Tournaments

Consider a network of (N) cities numbered from (1) to (N). For every two distinct cities, there is exactly one one‐way road connecting them (i.e. the network forms a tournament). A permit (or license) is required to drive on a road. Instead of assigning a distinct permit to each road, you must assign one of (K) different permits (numbered (1,2,\dots,K)) to every road. The assignment must satisfy the following property: for every city (v), there exists another city (u) ((u\neq v)) such that for every permit (c) ((1\le c\le K)) it is impossible to travel from (v) to (u) using only roads whose assigned permit is (c) (i.e. there is no monochromatic path from (v) to (u)).

Note that if there is a road from (v) to (u) then, by definition, there is no road from (u) to (v). In other words, for any two distinct cities, exactly one directed road exists. It can be shown that if the tournament has a vertex with outgoing degree (N-1) (called a source) then for that vertex every other city is directly reachable, and no assignment of permits can satisfy the property. In this case, the answer is (-1). Otherwise, one can prove that an assignment exists and the minimum possible (K) is (3).

Your task is to read the tournament description and, if a valid assignment exists, output the minimum (K) (which is (3)) and a valid assignment of permits to each road. Otherwise, output (-1).

All formulas must be typeset in (\LaTeX) format.

inputFormat

The first line contains a single integer (N) ((2 \le N \le 500)).

Then follow (N) lines. The (i)-th line is a string of (N) characters. The (j)-th character is either '1' or '0'. For (i \neq j), if the (j)-th character of the (i)-th line is '1', then there is a road from city (i) to city (j); otherwise (when it is '0'), the road goes from city (j) to city (i). It is guaranteed that the (i)-th character of the (i)-th line is '0'.

outputFormat

If there exists a valid permit assignment, print the minimum (K) (which is (3)) on the first line. Then print (N) lines, each containing (N) space‐separated integers. The (j)-th integer on the (i)-th line is the permit type assigned to the road from city (i) to city (j) if such a road exists; if (i = j) or if the road does not exist (because the road goes in the opposite direction), output (0) in that position.

If no valid assignment exists, output a single line with (-1).

An assignment is valid if for every city (v) there is some city (u) (with (u \neq v)) such that for every permit (c \in {1,2,3}), there is no path from (v) to (u) using only roads of permit (c).

sample

3
0 1 0
0 0 1
1 0 0

3
0 1 0
0 0 2
3 0 0