#include using namespace std; int n; int chk(int a) { if(a>=1 && a<=n ) return 1; return 0; } #define mp make_pair int solve(int a,int b) { vector > gp(n+1,vector(n+1,0)); queue > q; q.push(mp(1,1)); q.push(mp(-1,-1)); int l=0; while(!q.empty()) { pair p=q.front(); q.pop(); if(p.first==-1) { if(q.empty()) break; l++; q.push(mp(-1,-1)); } else { if(gp[p.first][p.second]==1) continue; gp[p.first][p.second]=1; if(p.first==p.second && p.first==n) { return l; } if(chk(p.first-a) && chk(p.second+b)) { q.push(mp(p.first-a,p.second+b)); } if(chk(p.first+a) && chk(p.second-b)) { q.push(mp(p.first+a,p.second-b)); } if(chk(p.first-a) && chk(p.second-b)) { q.push(mp(p.first-a,p.second-b)); } if(chk(p.first+a) && chk(p.second+b)) { q.push(mp(p.first+a,p.second+b)); } if(chk(p.first-b) && chk(p.second+a)) { q.push(mp(p.first-b,p.second+a)); } if(chk(p.first+b) && chk(p.second-a)) { q.push(mp(p.first+b,p.second-a)); } if(chk(p.first-b) && chk(p.second-a)) { q.push(mp(p.first-b,p.second-a)); } if(chk(p.first+b) && chk(p.second+a)) { q.push(mp(p.first+b,p.second+a)); } } } return -1; } int main() { ios_base::sync_with_stdio(0); cin>>n; vector > v(n+1,vector(n+1,0)); for(int i=1;i