#include <bits/stdc++.h>
using namespace std;
int n,cnt;
vector<pair<int,pair<int,int> > > p;
int fa[1050],v[1050],rfa[1050];
int ff(int i) {
	if (fa[i]==i) return i;
	return fa[i]=ff(fa[i]);
}
 
int main() {
	scanf("%d",&n); cnt=n;
	for (int i=1,x; i<=n; ++i)
		for (int j=1; j<=n; ++j) {
			scanf("%d",&x);
			if (j==i) {
				v[i]=x,fa[i]=i;
			} else if (i<j)
				p.push_back(make_pair(x,make_pair(i,j)));
		}
	sort(p.begin(),p.end());
	for (auto t:p) {
		int x=t.first,i=t.second.first,j=t.second.second;
		int fi=ff(i),fj=ff(j);
		if (fi!=fj) {
			if (v[fi]==x) fa[fj]=rfa[fj]=fi;
			else if (v[fj]==x) fa[fi]=rfa[fi]=fj;
			else {
				fa[fj]=rfa[fj]=fa[fi]=rfa[fi]=++cnt;
				fa[cnt]=cnt,v[cnt]=x;
			}
		}
	}
	cout<<cnt<<'\n';
	for (int i=1; i<=cnt; ++i) cout<<v[i]<<' ';
	cout<<'\n'<<cnt<<'\n';
	for (int i=1; i<cnt; ++i) cout<<i<<' '<<rfa[i]<<'\n';
}