#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <algorithm> #include <utility> #include <sstream> #include <iostream> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <cstdio> #include <cmath> #include <cstdlib> #include <climits> #define all(c) (c).begin(),(c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) #define ll long long #define sz(a) int((a).size()) #define pb push_back #define SORT(x) sort((x).begin(),(x).end()); #define VI vector<int> #define VII vector < vector <int> > #define MP make_pair #define SET(x,byte) memset(x,byte,sizeof(x)); #define I(x) ((x) - 'A') #define REP(i,mx) for(int i=0;(i)<(mx);i++) #define FOR(i,mn,mx) for(int i=mn;(i)<=(mx);i++) #define U(x) (1<<(x)) #define INF 1000000000 #define PI acos(-1) using namespace std; int num, nodeNum; vector<VI > vvi; int mult[] = {-1, 1}; bool isValid(int x, int y) { return (x >= 0 && x < num) && (y >= 0 && y < num); } int dijkstra(int start, int end, vector<VI > &vvi) { vector<char> mark(nodeNum, 0); VI path(nodeNum, INF); path[start] = 0; while(1) { int mn = INF, ind = -1; REP(i, nodeNum) { if(!mark[i] && path[i] < mn) { mn = path[i]; ind = i; } } if(ind == -1 || ind == end) break; //cout<<ind<<" is selected in dijkstra"<<endl; mark[ind] = 1; //cout<<"neighbours of it are:\n"; REP(i, sz(vvi[ind])) { //cout<<vvi[ind][i]<<" "; path[vvi[ind][i]] = min(path[vvi[ind][i]], path[ind]+1); } //cout<<endl; } //cout<<"dijkstra "<<start<<" "<<end<<" : "<<path[end]<<endl; return path[end]; } int solve(int a, int b) { //cout<<"solve for "<<a<<" and "<<b<<endl; int start = 0, end = nodeNum - 1; vector<VI > vvi(nodeNum); REP(i, num) { REP(j, num) { int node = i * num + j; REP(f, 2) { REP(h, 2) { int x = i + mult[f] * a; int y = j + mult[h] * b; if(isValid(x, y)) { int node2 = x * num + y; //cout<<"node:"<<node<<" node2:"<<node2<<endl; vvi[node].pb(node2); } } } REP(f, 2) { REP(h, 2) { int x = i + mult[f] * b; int y = j + mult[h] * a; if(isValid(x, y)) { int node2 = x * num + y; //cout<<"node:"<<node<<" node2:"<<node2<<endl; vvi[node].pb(node2); } } } } } return dijkstra(start, end, vvi); } int main() { cin>>num; nodeNum = num * num; REP(i, num-1) { VI vi(num-1, 0); vvi.pb(vi); } REP(i, num-1) { FOR(j, i, num-2) { vvi[i][j] = solve(i+1, j+1); vvi[j][i] = vvi[i][j]; } } REP(i, num-1) { REP(j, num-1) { if(vvi[i][j] == INF) cout<<"-1 "; else cout<<vvi[i][j]<<" "; } cout<<endl; } return 0; }