#!/bin/python import sys n = int(raw_input().strip()) # your code goes here def next_step(current_pos, i, j, step,visited): #print n #print visited if current_pos == (n-1, n-1): print step, return 1 step += 1 next_positions = [] next_positions.append((current_pos[0]+i, current_pos[1]+j)) next_positions.append((current_pos[0]+j, current_pos[1]+i)) next_positions.append((current_pos[0]-i, current_pos[1]+j)) next_positions.append((current_pos[0]-j, current_pos[1]+i)) next_positions.append((current_pos[0]+i, current_pos[1]-j)) next_positions.append((current_pos[0]+j, current_pos[1]-i)) not_visited =[] for pos in next_positions: if pos[0] >=0 and pos[0] <= n-1 and pos[1]>=0 and pos[1] <= n-1: if pos not in visited.keys(): visited[pos] = step not_visited.append(pos) #if len(not_visited) == 0 and (n-1, n-1) not in visited: # flag = False # return flag if len(not_visited) == 0: return 0 else: for pos2 in not_visited: return next_step(pos2, i, j, step, visited) for i in range(1,n): for j in range(1,n): if (i,j) == (1,1): print n-1, elif (i,j) == (n-1, n-1): print 1, else: step = 0 current_pos = (0,0) visited = {(0,0):0} flag = 0 flag = next_step(current_pos,i,j,step,visited) if flag == 1: next else: print -1, print