#include<bits/stdc++.h>
using namespace std;

const int maxn = 500;
const int maxm = 3e5+10;
int a[maxn][maxn],val[maxn];
struct node
{
	int x,y,z;
	node(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
}e[maxm];
bool cmp(node a,node b)
{
	if(a.z==b.z) return a.x<b.x;
	return a.z<b.z;
}
vector<int>g[maxm];
int f[maxm];
int find(int u)
{
	return f[u]==u?u:f[u] = find(f[u]);
}

int main()
{
	int n,now = 0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			if(i==j) val[i]=a[i][j];
			else if(j>i)
			{
				e[++now]=node(i,j,a[i][j]);
			}
		}
	}
	sort(e+1,e+1+now,cmp);
	for(int i=0;i<maxm;i++)
	{
		f[i]=i;
	}
	int cur=n;
	for(int i=1;i<=now;i++)
	{
		int u=e[i].x,v=e[i].y,num=e[i].z;
		u=find(u);v=find(v);
		if(u==v) continue;
		else if(cur==u&&val[cur]==num)
		{
			f[v]=cur;
			g[cur].push_back(v);
		}
		else
		{
			cur++;
			f[u]=cur,f[v]=cur;
			g[cur].push_back(u),g[cur].push_back(v),val[cur]=num;
		}
	}
	
	cout<<cur<<endl;
	for(int i=1;i<=cur;i++) cout<<val[i]<<" ";
	cout<<endl;
	cout<<find(1)<<endl;
	for(int i=1;i<=cur;i++)
	{
		for(int j=0;j<g[i].size();j++)
		{
			cout<<g[i][j]<<" "<<i<<endl;
		}
	}
}