import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int n; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); // your code goes here Node[][] nodes=new Node[n][n]; for(int i=0;i list){ int least=1000000000; int l=-1; for(int i=0;i list = new ArrayList<>(); for(int i=0;i=0){ nodes[i][j].links.add(nodes[i+x][j-y]); nodes[i][j].links.add(nodes[j-y][i+x]); } } if(i-x>=0){ if(j+y=0){ nodes[i][j].links.add(nodes[i-x][j-y]); nodes[i][j].links.add(nodes[j-y][i-x]); } } } } nodes[n-1][n-1].dist=0; dijkstra(list); if(nodes[0][0].dist==1000000) return -1; return nodes[0][0].dist; } public static void dijkstra(ArrayList list){ if(list.isEmpty()) return; Node node=removeLeast(list); node.notUsed=false; for(int i=0;inode.dist+1){ temp.dist=node.dist+1; if(temp.x==0 && temp.y==0){ return; } } } } dijkstra(list); } } class Node{ ArrayList links; public int x; public int y; public int dist; boolean notUsed; Node(int z, int q){ x=z; y=q; dist=1000000; links=new ArrayList<>(); notUsed=true; } }