AT_utpc2024_e.Edge Coloring Problem

给定一个 $N$ 个顶点、$\frac{N(N-3)}{2}$ 条边构成的简单无向图。该图由 $N$ 个仅包含 0 和 1 的字符串 $S_1, S_2, \dots, S_N$ 表示。如果 $S_i$ 的第 $j$ 个字符为 1，则表示顶点 $i$ 和 $j$ 之间存在一条边；为 0 时则不存在此边。特别地，$S_i$ 的第 $i$ 个字符必为 `0$。

该图中每个顶点的度数均为 $N-3$。

现要求为该图的每条边分配一个不小于 $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$。

如果存在多种符合要求的输出方案，输出任意一种即可。

样例解释 1

顶点 $1$ 与顶点 $2, 3, 4$ 相连，这三条边必须被分配为互不相同的整数，因此边着色数至少为 $3$。

如样例输出所分配的整数，顶点 $1$ 与顶点 $2, 3, 4$ 间边被分别分配为 $2, 3, 1$，各不相同。对于其他顶点 $v$ 也同理，可以确认以 $v$ 为端点的各条边分配的整数互不相同。

因此，输出是一种合法的边着色方式，且边着色数为 $3$。

数据范围

• $4 \leq N \leq 300$
• $S_1,S_2,\dots,S_N$ 均为长度为 $N$ 的仅包含 0 和 1 的字符串
• 所给图是每个顶点度数均为 $N-3$ 的简单无向图

由 ChatGPT 5 翻译