#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
 
ll ksm(ll x,ll k) {
	ll ret=1;
	while(k) {
		if(k&1)	ret=ret*x%mod;
		x=x*x%mod,k>>=1;
	}
	return ret;
}
 
ll prime[10000005],pcnt,phi[10000005];
bool mark[10000005];
inline void pre(ll n) {
	mark[1]=1;
	for(ll i=2;i<=n;i++) {
		if(!mark[i])	prime[++pcnt]=i/*,phi[i]=i-1*/;
		for(ll j=1;j<=pcnt;j++) {
			ll k=i*prime[j];
			if(k>n)	break;
			mark[k]=1;
			if(i%prime[j]==0) {
//				phi[k]=phi[i]*prime[j];
				break;
			}
//			else	phi[k]=phi[i]*(prime[j]-1);
		}
	}
}

struct data {
	int u,v,val;
	data(int _u=0,int _v=0,int _val=0):u(_u),v(_v),val(_val) {}
	bool operator < (const data &x) const {
		if(val==x.val)	return u<x.u;
		return val<x.val;
	}
}a[505*505];
int fa[505*505],c[505*505];
vector <int> u,v;

int getfa(int x) {
	return x==fa[x] ? x:fa[x]=getfa(fa[x]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T=1;
//	cin>>T;
	while(T--) {
		int n; cin>>n;
		for(int i=1;i<=n*n;i++)	fa[i]=i;
		int cnt=0;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				int x; cin>>x;
				if(i==j)	c[i]=x;
				if(i>=j)	continue;
				a[++cnt]=data(i,j,x);
			}
		}
		sort(a+1,a+cnt+1);
		int k=n;
		for(int i=1;i<=cnt;i++) {
			int fu=getfa(a[i].u),fv=getfa(a[i].v);
			if(fu==fv)	continue;
			if(fu>n && c[fu]==a[i].val) {
				fa[fv]=fu,u.push_back(fv),v.push_back(fu);
				continue;
			}
			if(fv>n && c[fv]==a[i].val) {
				fa[fu]=fv,u.push_back(fu),v.push_back(fv);
				continue;
			}
			k++;
			fa[fu]=fa[fv]=k;
			c[k]=a[i].val;
			u.push_back(fu),v.push_back(k);
			u.push_back(fv),v.push_back(k);
		}
		cout<<k<<"\n";
		for(int i=1;i<=k;i++)	cout<<c[i]<<" ";
		cout<<"\n";
		cout<<k<<"\n";
		for(int i=0;i<u.size();i++)	cout<<u[i]<<" "<<v[i]<<"\n";
	}
}
