import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int boardsize = in.nextInt(); //0 - boardsize-1 for(int a=1; a current = new LinkedList<>(); Queue neighbors = new LinkedList<>(); current.add(new Coordinate(0,0)); int minMoves = 0; Board board = new Board(boardsize); //System.out.println("Knight " + a + b); while(!current.isEmpty()){ Coordinate currentCoord = current.remove(); //System.out.println("Current to check size: " + current.size()); neighbors.addAll(board.getNeighborCoordinates(a, b, currentCoord)); //System.out.println("Current to check size: " + current.size()); //print(currentCoord, neighbors, current); if(containsEnd(neighbors, boardsize)){ System.out.print((minMoves+1) + " "); break; } if(current.isEmpty() && neighbors.isEmpty()){ System.out.print(-1 + " "); break; } if(current.isEmpty()){ current = new LinkedList(); current.addAll(neighbors); neighbors.clear(); minMoves++; //System.out.println("Adding to min moves: " + minMoves); } } } System.out.println(); } //ret } public static void print(Coordinate current, Queue neighbors, Queue currentCoords){ System.out.println("Current coord is : (" + current.getX() + "," + current.getY() + ")"); System.out.println("Current Coords are : "); for(Coordinate coord1 : currentCoords){ System.out.println("(" + coord1.getX() + "," + coord1.getY() + ") "); } System.out.println("Neighbors are : "); for(Coordinate coord : neighbors){ System.out.println("(" + coord.getX() + "," + coord.getY() + ") "); } System.out.println(); } public static Boolean containsEnd(Queue arr, int boardsize){ for(Coordinate coord : arr){ if(coord.getX() == boardsize-1 && coord.getY() == boardsize-1){ return true; } } return false; } public static class Board{ int[][] board; int boardsize; public Board(int boardsize){ this.board = new int[boardsize][boardsize]; this.boardsize = boardsize; board[0][0] = 1; } public LinkedList getNeighborCoordinates(int a, int b, Coordinate current){ LinkedList arr = new LinkedList<>(); if(current.getX()+a < boardsize && current.getY()+b < boardsize && board[current.getX()+a][current.getY()+b] != 1){ //System.out.println("Added up right : (" + (current.getX()+a) + "," + (current.getY()+b) + ")"); arr.add(new Coordinate(current.getX()+a, current.getY()+b)); board[current.getX()+a][current.getY()+b] = 1; } if(current.getX()+b < boardsize && current.getY()+a < boardsize && board[current.getX()+b][current.getY()+a] != 1){ //System.out.println("Added right up : (" + (current.getX()+b) + "," + (current.getY()+a) + ")"); arr.add(new Coordinate(current.getX()+b, current.getY()+a)); board[current.getX()+b][current.getY()+a] = 1; } if(current.getX()+b < boardsize && current.getY()-a >=0 && board[current.getX()+b][current.getY()-a] != 1){ //System.out.println("Added right down : (" + (current.getX()+b) + "," + (current.getY()-a) + ")"); arr.add(new Coordinate(current.getX()+b, current.getY()-a)); board[current.getX()+b][current.getY()-a] = 1; } if(current.getX()+a < boardsize && current.getY()-b >=0 && board[current.getX()+a][current.getY()-b] != 1){ //System.out.println("Added bottom right : (" + (current.getX()+a) + "," + (current.getY()-b) + ")"); arr.add(new Coordinate(current.getX()+a, current.getY()-b)); board[current.getX()+a][current.getY()-b] = 1; } if(current.getX()-a >= 0 && current.getY()-b >= 0 && board[current.getX()-a][current.getY()-b] != 1){ //System.out.println("Added bottom left : (" + (current.getX()-a) + "," + (current.getY()-b) + ")"); arr.add(new Coordinate(current.getX()-a, current.getY()-b)); board[current.getX()-a][current.getY()-b] = 1; } if(current.getX()-b >= 0 && current.getY()-a >= 0 && board[current.getX()-b][current.getY()-a] != 1){ //System.out.println("Added left down : (" + (current.getX()-b) + "," + (current.getY()-a) + ")"); arr.add(new Coordinate(current.getX()-b, current.getY()-a)); board[current.getX()-b][current.getY()-a] = 1; } if(current.getX()-b >= 0 && current.getY()+a < boardsize && board[current.getX()-b][current.getY()+a] != 1){ //System.out.println("Added left up : (" + (current.getX()-b) + "," + (current.getY()+a) + ")"); arr.add(new Coordinate(current.getX()-b, current.getY()+a)); board[current.getX()-b][current.getY()+a] = 1; } if(current.getX()-a >= 0 && current.getY()+b < boardsize && board[current.getX()-a][current.getY()+b] != 1){ //System.out.println("Added up left : (" + (current.getX()-a) + "," + (current.getY()+b) + ")"); arr.add(new Coordinate(current.getX()-a, current.getY()+b)); board[current.getX()-a][current.getY()+b] = 1; } return arr; } } public static class Coordinate{ int x; int y; public Coordinate(int x, int y){ this.x = x; this.y = y; } public int getX(){ return x; } public int getY(){ return y; } } }