#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w const int MAXN=1510; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} int n,ans,cnt; vector<pii>p[MAXN*MAXN]; pair<pii,int>c[MAXN*MAXN]; void add(int x,int y,int z){if(z)c[++cnt]=mk(mk(x,y),z);} int it[MAXN],mt[MAXN][MAXN],col[MAXN*MAXN]; void upd(int x){ it[x]=0; while(mt[it[x]][x])it[x]++; } pii s[MAXN*MAXN]; int T[MAXN][MAXN],S[MAXN][MAXN]; bool chk(){ for(int i=1;i<=n*n;i++)for(auto o:p[i])T[o.fr][o.sc]=i; for(int i=1;i<=cnt;i++)S[c[i].fr.fr][c[i].fr.sc]=c[i].sc; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ // cout<<i<<" "<<j<<" "<<k<<" "<<T[i][j]<<" "<<S[i][j]<<" "<<T[i][k]<<" "<<S[i][k]<<" "<<T[k][j]<<" "<<S[k][j]<<endl; if(k!=j&&mk(T[i][j],S[i][j])==mk(T[i][k],S[i][k]))return 0; if(k!=i&&mk(T[i][j],S[i][j])==mk(T[k][j],S[k][j]))return 0; } } } return 1; } void dfs(int id,int x,int y){ int u=s[id].fr,v=s[id].sc; int tmp=0; if(mt[col[id]][u]==id)tmp=mt[x][u],mt[col[id]][u]=0; else tmp=mt[x][v],mt[col[id]][v]=0; col[id]=x; mt[x][u]=mt[x][v]=id; if(tmp)dfs(tmp,y,x); } void sol(int u,int v,int id){ upd(u),upd(v); int x=it[u],y=it[v]; if(x<y){ col[id]=x; int tmp=mt[x][v]; mt[col[id]][u]=mt[col[id]][v]=id; if(tmp)dfs(tmp,y,x); } else { col[id]=y; int tmp=mt[y][u]; mt[col[id]][u]=mt[col[id]][v]=id; if(tmp)dfs(tmp,x,y); } } int sol(int x){ int res=0; memset(mt,0,sizeof(mt)); memset(it,0,sizeof(it)); memset(col,0,sizeof(col)); for(int i=0;i<p[x].size();i++)s[i+1]={p[x][i].fr,p[x][i].sc+n}; for(int i=1;i<=p[x].size();i++)col[i]=0,sol(s[i].fr,s[i].sc,i); for(int i=1;i<=p[x].size();i++)mt[col[i]][s[i].fr]=mt[col[i]][s[i].sc]=0,add(s[i].fr,s[i].sc-n,col[i]),res=max(res,col[i]); for(int i=1;i<=n<<1;i++)it[i]=0; return res; } void slv(){ n=read(); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){ int x=read(); p[x].pb(mk(i,j)); } for(int i=1;i<=n*n;i++)if(!p[i].empty())ans=max(ans,sol(i)); printf("%d %d\n",ans,cnt); for(int i=1;i<=cnt;i++)printf("%d %d %d\n",c[i].fr.fr,c[i].fr.sc,c[i].sc); // assert(chk()); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); return 0; }