// LUOGU_RID: 99122385
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001;
struct node {
	int u,v,w;
	inline friend bool operator <(const node &A,const node &B) {
		return A.w<B.w;
	}
};
vector <node> edges;
vector <int> G[MAXN];
int w[MAXN][MAXN],id[MAXN],val[MAXN],dsu[MAXN];
bool del[MAXN];
inline int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x]=find(dsu[x]);
}
signed main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) dsu[i]=i;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d",&w[i][j]);
			if(i<j) edges.push_back((node){i,j,w[i][j]});
			if(i==j) val[i]=w[i][i];
		}
	}
	sort(edges.begin(),edges.end());
	int siz=n;
	for(auto e:edges) {
		int x=find(e.u),y=find(e.v);
		if(x==y) continue;
		if(val[x]==e.w&&val[y]==e.w) {
			del[y]=true,dsu[y]=x;
			for(int i:G[y]) G[x].push_back(i);
			G[y].clear();
		} else if(val[x]==e.w) {
			dsu[y]=x;
			G[x].push_back(y);
		} else if(val[y]==e.w) {
			dsu[x]=y;
			G[y].push_back(x);
		} else {
			dsu[x]=dsu[y]=++siz;
			dsu[siz]=siz,val[siz]=e.w;
			G[siz].push_back(x),G[siz].push_back(y);
		}
	}
	int idcnt=0;
	for(int i=1;i<=siz;++i) if(!del[i]) id[i]=++idcnt;
	printf("%d\n",idcnt);
	for(int i=1;i<=siz;++i) if(!del[i]) printf("%d ",val[i]); puts("");
	printf("%d\n",idcnt);
	for(int i=1;i<=siz;++i) {
		if(del[i]) continue;
		for(int j:G[i]) printf("%d %d\n",id[j],id[i]);
	}
	return 0;
}