import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private int bestSolution; private int[] visited; private int n; private int f; private int c; public Solution(int n, int f, int c) { this.n = n; this.f = f; this.c = c; visited = new int[n*n]; bestSolution = 15; for (int i = 0; i < visited.length; i++) { visited[i] = -1; } } public void generateMovement(List cells, int fc, int cc, int af, int ac) { int nf = fc + af; int nc = cc + ac; if (nf >= 0 && nf < n && nc >= 0 && nc < n) { int nn = n * nf + nc; cells.add(nn); } } public List generateMovements(int position) { int fc = position / n; int cc = position % n; List result = new ArrayList<>(); generateMovement(result, fc, cc, f, c); generateMovement(result, fc, cc, f, -c); generateMovement(result, fc, cc, -f, c); generateMovement(result, fc, cc, -f, -c); generateMovement(result, fc, cc, c, f); generateMovement(result, fc, cc, c, -f); generateMovement(result, fc, cc, -c, f); generateMovement(result, fc, cc, -c, -f); return result; } public boolean isSolution(int current) { return current == n*n-1; } public boolean searchPath(List cells, int level) { if (cells.isEmpty()) { return false; } if (bestSolution <= level) { return false; } //System.out.println(bestSolution); for (Integer current : cells) { if (isSolution(current)) { if (level < bestSolution) { bestSolution = level; continue; } } if (visited[current] != -1 && visited[current] < level) { continue; } visited[current] = level; List next = generateMovements(current); searchPath(next, level+1); } return true; } public static void main(String[] args) { //long time = System.currentTimeMillis(); Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int rsize = n-1; int[] results = new int[rsize*rsize]; for (int i = 1; i < n; i++) { for (int j = i; j < n; j++) { Solution k = new Solution(n, i, j); List next = k.generateMovements(0); k.searchPath(next, 1); results[(i-1)*rsize+(j-1)] = k.bestSolution == 15 ? -1 : k.bestSolution; results[(j-1)*rsize+(i-1)] = k.bestSolution == 15 ? -1 : k.bestSolution; } } for (int i = 0; i < rsize; i++) { for (int j = 0; j < rsize; j++) { System.out.print(results[i*rsize+j] + " "); } System.out.println(""); } //System.out.println("Time: " + (System.currentTimeMillis() - time + "m s ")); } }