#!/bin/python import sys def find_steps(board, n, i, j, x=0, y=0): best_steps = float('inf') if x+i < n: if y+j < n: if board[x+i][y+j] > board[x][y]+1: board[x+i][y+j] = board[x][y]+1 find_steps(board, n, i, j, x+i, y+j) if y-j >= 0: if board[x+i][y-j] > board[x][y]+1: board[x+i][y-j] = board[x][y]+1 find_steps(board, n, i, j, x+i, y-j) if x+j < n: if y+i < n: if board[x+j][y+i] > board[x][y]+1: board[x+j][y+i] = board[x][y]+1 find_steps(board, n, i, j, x+j, y+i) if y-i >= 0: if board[x+j][y-i] > board[x][y]+1: board[x+j][y-i] = board[x][y]+1 find_steps(board, n, i, j, x+j, y-i) if x-i >= 0: if y+j < n: if board[x-i][y+j] > board[x][y]+1: board[x-i][y+j] = board[x][y]+1 find_steps(board, n, i, j, x-i, y+j) if y-j >= 0: if board[x-i][y-j] > board[x][y]+1: board[x-i][y-j] = board[x][y]+1 find_steps(board, n, i, j, x-i, y-j) if x-j >= 0: if y+i < n: if board[x-j][y+i] > board[x][y]+1: board[x-j][y+i] = board[x][y]+1 find_steps(board, n, i, j, x-j, y+i) if y-i >= 0: if board[x-j][y-i] > board[x][y]+1: board[x-j][y-i] = board[x][y]+1 find_steps(board, n, i, j, x-j, y-i) n = int(raw_input().strip()) # your code goes here for i in range(1,n): for j in range(1,n): if i == 1 and j == 1: print n-1, else: board = [[float('inf') for x in range(n)] for y in range(n)] board[0][0] = 0 find_steps(board, n, i, j) if board[n-1][n-1] != float('inf'): print board[n-1][n-1], else: print -1, print ''