18913번 - Graph Coloring 스페셜 저지다국어

You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i \to j$ and $j \to i$), with $n \leq 3000$ vertices. You need to color its edges into $14$ colors.

There should be no path $i \to j \to k$ in this graph such that the colors of edges $i \to j$ and $j \to k$ are the same.

It is guaranteed that this is always possible.

The first line of input contains one integer $n$ ($3 \leq n \leq 3000$): the number of vertices in the given tournament.

Next $n-1$ lines contain the description of the graph: the $i$-th line contains a binary string with $i$ characters.

If the $j$-th character in this string is equal to '1', then the graph has an edge from $(i + 1) \to j$. Otherwise, it has an edge from $j \to (i+1)$.

The output should contain $n-1$ lines, where the $i$-th line contains a string with $i$ characters.

The $j$-th character in this string should be a lowercase Latin letter between 'a' and 'n'. If the graph has an edge from $(i + 1) \to j$, then this character represents the color of the edge from $(i + 1) \to j$. Otherwise it represents the color of the edge from $j \to (i + 1)$.

There should be no path $i \to j \to k$ in this graph such that the colors of edges $i \to j$ and $j \to k$ are the same.