AT_utpc2024_e Edge Coloring Problem

$ N $ 頂点 $ \frac{N(N-3)}{2} $ 辺からなる単純無向グラフが与えられます。グラフは `0`,`1` のみからなる $ N $ 個の文字列 $ S_1, S_2, \dots, S_{N} $ で表され、 $ S_i $ の $ j $ 文字目が `1` の場合頂点 $ i, j $ を結ぶ辺が存在することを、 `0` の場合存在しないことを表します。特に、 $ S_i $ の $ i $ 文字目は必ず `0` です。 このグラフの各頂点の次数はいずれも $ N-3 $ です。 これからグラフの各辺に $ 1 $ 以上の整数を割り当てることを考えます。このとき、共通の頂点を端点にもつどの $ 2 $ 辺についても互いに相異なる整数が割り当てられているような割当を辺彩色といい、辺彩色に用いられる整数の最大値として考えられる値の最小値を辺彩色数といいます。 グラフの辺彩色数を求め、実際にそれを達成する辺彩色を $ 1 $ つ求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_{N} $

辺彩色数 $ C $ と頂点 $ i,j $ を結ぶ辺に割り当てる整数 $ c_{i,j} $ について、以下の形式で出力せよ。 > $ C $ $ c_{1,1} $ $ c_{1,2} $ $ \dots $ $ c_{1,N} $ $ c_{2,1} $ $ c_{2,2} $ $ \dots $ $ c_{2,N} $ $ \vdots $ $ c_{N,1} $ $ c_{N,2} $ $ \dots $ $ c_{N,N} $ ただし、頂点 $ i,j $ を結ぶ辺が存在しないような $ i,j $ に対しては $ c_{i,j}=-1 $ として出力せよ。とくに $ c_{i,i} $ については $ c_{i,i}=-1 $ として出力せよ。 条件を満たす出力が複数存在する場合、いずれの出力も正当とみなされる。

### Sample Explanation 1 頂点 $ 1 $ は頂点 $ 2,3,4 $ と結ばれており、これらの辺には互いに相異なる整数を割り当てなければならないので、辺彩色数は $ 3 $ 以上です。 出力のように整数を割り当てると、例えば頂点 $ 1 $ と頂点 $ 2,3,4 $ を結ぶ辺にはそれぞれ整数 $ 2,3,1 $ が割り当てられており、互いに相異なります。他の頂点 $ v $ についても同様に $ v $ を端点とする辺には互いに相異なる整数が割り当てられていることが確認できます。よって出力は辺彩色になっており、辺彩色数は $ 3 $ であるとわかります。 ### Constraints - $ 4 \leq N \leq 300 $ - $ S_1,S_2,\dots,S_N $ は `0`,`1` のみからなる長さ $ N $ の文字列 - 与えられるグラフは各頂点の次数が $ N-3 $ であるような単純無向グラフ