#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int mat[505][505];
int fa[10000];
int salary[10000];
int main()
{
   	int n;
	scanf("%d",&n);
	int k = n-1;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++)
			scanf("%d",&mat[i][j]);
	for(int i = 0;i < n;i++)
	{
		//printf("process %d\n",i);
		salary[i] = mat[i][i];
		int min_sal = 5001;
		int pos = -1;
		for(int j = 0;j < i;j++)
		{
			if( mat[i][j] < min_sal )
			{
				min_sal = mat[i][j];
				pos = j;
			}
		}
		while(pos != -1 && salary[pos] != min_sal)
		{
			pos = fa[pos];
		}
		if( i != n-1 )
		{
			sort(mat[i]+i,mat[i]+n);
			//for(int j = 0;j < n;j++)
				//printf("%d ",mat[i][j]);
			//printf("\n",pos,min_sal);
			int pre_sal = -1;
			int processId = i;
			for(int j = i+1;j < n;j++)
			{
				if( pre_sal == mat[i][j] )
					continue;
				pre_sal = mat[i][j];
				if( mat[i][j] >= min_sal && i != 0 )
				{
					fa[processId] = pos;
					break;
				}
				else{
					k++;
					salary[k] = mat[i][j];
					fa[processId] = k;
					//printf("%d %d\n",processId,fa[processId]);
					processId = k;
					
				}
			}
			if( fa[processId] == 0 )
				fa[processId] = pos;
		}
		else{
			fa[i] = pos;
		}
	}
	printf("%d\n",k+1);
	for(int i = 0;i <= k;i++)
		printf("%d ",salary[i]);
	printf("\n");
	int max_sal = 0;
	int boss = -1;
	for(int i = 0;i <= k;i++)
		if( salary[i] > max_sal )
		{
			max_sal = salary[i];
			boss = i;
		}
	printf("%d\n",boss+1);
	for(int i = 0;i <= k;i++)
	{
		if( i != boss )
			printf("%d %d\n",i+1,fa[i]+1);
	}
		
}