配点 : 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