#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair using namespace std; const int N=1250; int a[N][N],n; struct op{ int a,b,c; };vector<op> opt; void add(int a,int b,int c){ if(c){opt.push_back((op){a,b,c});} } bool ok=0; pii edge[N]; int clr[N][N],b[N][N]; int to[N][N]; int du[N]; vector<pii> vec[N*N]; int mex(int id){ for(int i=0;i<=n;i++) if(!to[id][i]) return i; } int solve(int c){ for(auto ed:vec[c]){ int u=ed.fi,v=ed.se;v+=n; //cout<<c<<' '<<u<<' '<<v<<endl; du[v]++;du[u]++; int clr1=mex(u),clr2=mex(v); clr[u][v]=clr1;clr[v][u]=clr1; to[v][clr2]=to[v][clr1]; to[v][clr1]=u;to[u][clr1]=v; if(clr1==clr2) continue; for(int now=v,c=clr2;;c^=(clr1^clr2)){ int cf=c^clr1^clr2; int x=to[now][c]; if(!x) break; clr[x][now]=c;clr[now][x]=c; to[x][cf]=to[x][c]; to[x][c]=now;now=x; } } int ans=0; for(int i=1;i<=n*2;i++) ans=max(ans,du[i]); for(auto ed:vec[c]){ int u=ed.fi,v=ed.se;v+=n; du[u]--;du[v]--; int c=clr[u][v]; b[u][v-n]=c; //cout<<u<<' '<<v-n<<' '<<c<<endl; clr[u][v]=0;clr[v][u]=0; to[u][c]=0;to[v][c]=0; }return ans-1; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; vec[a[i][j]].push_back(mk(i,j)); } } int w=0; for(int i=1;i<=n*n;i++) w=max(solve(i),w); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ add(i,j,b[i][j]); } } cout<<w<<' '<<opt.size()<<endl; for(auto ed:opt) cout<<ed.a<<' '<<ed.b<<' '<<ed.c<<'\n'; cout.flush(); /*cout<<600<<endl; for(int i=1;i<=600;i++){ for(int j=1;j<=600;j++){ cout<<rand()%600<<' '; }cout<<endl; }*/ return 0; }