#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define forn(i,n) for(int i=0;i<(int)(n); i++) #define forsn(i,s,n) for(int i=(s);i<(int)(n); i++) #define esta(x,v) (find((v).begin(),(v).end(),(x)) != (v).end()) #define index(x,v) (find((v).begin(),(v).end(),(x)) - (v).begin()) #define debug(x) cout << #x << " = " << x << endl #define pb push_back #define mp make_pair typedef long long tint; typedef unsigned long long utint; typedef long double ldouble; typedef vector vint; int toNumber (string s) { int Number; if ( ! (istringstream(s) >> Number) ) Number = 0; // el string vacio lo manda al cero return Number; } string toString (int number) { ostringstream ostr; ostr << number; return ostr.str(); } int main (){ int n; cin>>n; vector< pair > dir; dir.pb(mp(1,1)); dir.pb(mp(1,-1)); dir.pb(mp(-1,1)); dir.pb(mp(-1,-1)); int INF=n*n*n; forsn(i, 1, n){ forsn(j, 1, n){ queue< pair > > q; q.push(mp(0, mp(0,0))); int cant[n][n]; forn(a, n){ forn(b,n){ cant[a][b]=INF; } } int a=i; int b=j; cant[0][0]=0; while(!q.empty()){ pair > toy=q.front(); q.pop(); int tx=toy.second.first; int ty=toy.second.second; forn(k, 4){ if(tx+a*dir[k].first>=0 && tx+a*dir[k].first=0 && ty+b*dir[k].secondtoy.first+1){ q.push(mp(toy.first+1, mp(nx, ny))); cant[nx][ny]=toy.first+1; } } if(tx+b*dir[k].first>=0 && tx+b*dir[k].first=0 && ty+a*dir[k].secondtoy.first+1){ q.push(mp(toy.first+1, mp(nx, ny))); cant[nx][ny]=toy.first+1; } } } } if(cant[n-1][n-1]==INF){ cout<<-1; }else{ cout<