/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
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 つ求めてください。
制約
- 4 \leq N \leq 300
- S_1,S_2,\dots,S_N は
0,1のみからなる長さ N の文字列 - 与えられるグラフは各頂点の次数が N-3 であるような単純無向グラフ
入力
入力は以下の形式で標準入力から与えられる。
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 として出力せよ。
条件を満たす出力が複数存在する場合、いずれの出力も正当とみなされる。
入力例 1
6 011100 101010 110001 100011 010101 001110
出力例 1
3 -1 2 3 1 -1 -1 2 -1 1 -1 3 -1 3 1 -1 -1 -1 2 1 -1 -1 -1 2 3 -1 3 -1 2 -1 1 -1 -1 2 3 1 -1
頂点 1 は頂点 2,3,4 と結ばれており、これらの辺には互いに相異なる整数を割り当てなければならないので、辺彩色数は 3 以上です。
出力のように整数を割り当てると、例えば頂点 1 と頂点 2,3,4 を結ぶ辺にはそれぞれ整数 2,3,1 が割り当てられており、互いに相異なります。他の頂点 v についても同様に v を端点とする辺には互いに相異なる整数が割り当てられていることが確認できます。よって出力は辺彩色になっており、辺彩色数は 3 であるとわかります。
入力例 2
5 01001 10100 01010 00101 10010
出力例 2
3 -1 2 -1 -1 1 2 -1 3 -1 -1 -1 3 -1 1 -1 -1 -1 1 -1 3 1 -1 -1 3 -1