Edge Labeling on Complete Graph Avoiding Monochromatic Cycles

Given an undirected complete graph with n nodes, assign a digit from 0 to 9 to each edge such that there is no 3-cycle (triangle) or 5-cycle (pentagon) in which all edges have the same digit. In other words, for every cycle of length 3 or 5, at least one edge must have a digit different from the others.

You are required to output a valid labeling in the form of an n×n matrix. The element in the i-th row and j-th column represents the digit assigned to the edge connecting node i and node j (if i ≠ j), and a '*' character if i equals j (since there is no self-loop).

It can be proven that under the constraints provided, a valid labeling exists. One simple construction is to assign each edge (i, j) with the value |i - j| (using 0-indexing) when i ≠ j. Under the assumption that n is at most 10, this construction guarantees that for any 3-cycle or 5-cycle the five (or three) values will not all be identical. (Note: The indices are taken from 0 to n-1 in the solution code; when printing the matrix, the diagonal is replaced with '*' as required.)

Mathematical formulation:

Let the digit assigned to edge (i, j) be defined as \[ f(i,j)=\begin{cases} |i-j|, & i \neq j, \\ *, & i=j. \end{cases} \] Then for any cycle of length 3 or 5, it is guaranteed that not all of the corresponding edge values are equal.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10), the number of nodes in the graph.

outputFormat

Output an n×n matrix. For each 1 ≤ i ≤ n, print a line containing n items separated by spaces. For j from 1 to n, if i = j, output '*' (without quotes); otherwise, output the digit assigned to the edge connecting node i and node j. The matrix must be symmetric.

sample

3

* 1 2
1 * 1
2 1 *