← 返回题目列表

AtCoder · utpc2024_e

E. 边缘着色问题

中文机器翻译题面 查看原题

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