#include <bits/stdc++.h>
#define forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fst first
#define snd second

#ifdef ANARAP
#define MAXN 13
#else
#define MAXN 502
#endif

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

int mx[MAXN][MAXN];
bool used[MAXN][MAXN];
struct UnionFind{
	vector<int> f, setSize; //the array f contains the parent of each node
	int cantSets;
	void init(int n)
	{
		f.clear(); setSize.clear();
		cantSets = n;
		f.rsz(n, -1);
		setSize.rsz(n, 1);
	}
	int comp(int x) {return (f[x]==-1? x : f[x]=comp(f[x]));}//O(1)
	bool join(int a, int b) //devuelve true si ya estaban juntos
	{
		a=comp(a), b= comp(b);
		if(a!=b){
			setSize[b] += setSize[a];
			f[a] = b; //el grupo mas grande (b) ahora representa al mas chico (a)
		}
		return a == b;
	}
}uf;

int main()
{
	#ifdef ANARAP
		freopen("input.in", "r", stdin);
		//freopen("output.out", "w", stdout);
		unsigned t0, t1; t0=clock();
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n; cin >> n;
	vector<int> ans(n), apunta(n, -1);
	forn(i,n) forn(j,n) cin >> mx[i][j];
	forn(i,n) ans[i] = mx[i][i];
	int row = -1;
	int mini = 5001;
	forn(i,n)forr(j,i+1,n)if(mx[i][j]<mini) {row = i; mini = mx[i][j];}
	int node=n;
	uf.init(n*2+10);
	vector<int> rows;
	forr(j, row+1, n){
		if(mx[row][j] == mini){
			used[row][j] = 1;
			rows.pb(j);
			uf.join(j, node);
			apunta[j] = node;
		} 
	}
	forn(i,sz(rows)){
		forr(j, rows[i]+1, n){
			if(mx[rows[i]][j] == mini) used[rows[i]][j]=1;
		}
	}
	apunta[row] = node;
	uf.join(row, node);
	ans.pb(mini);
	apunta.pb(-1);
	while(1){
		node++;
		row = -1;
		mini = 5001;
		rows.clear();
		forn(i,n)forr(j,i+1,n)if(!used[i][j] && mx[i][j]<mini) {row = i; mini = mx[i][j];}
		//~ forn(i,n){
			//~ forn(j,n) cout << used[i][j] << " ";
			//~ cout << '\n';
		//~ }
		//~ cout << row << endl;
		if(row==-1) break;
		ans.pb(mini);
		apunta.pb(-1);
		int auxrow = uf.comp(row);
		forn(i,n)if(uf.comp(i) == auxrow) {rows.pb(i);}
		apunta[auxrow] = node;
		uf.join(auxrow, node);
		vector<int> rows2;
		forn(i, sz(rows)){
			forr(j, rows[i], n){
				if(!used[rows[i]][j] && mx[rows[i]][j] == mini){
					used[rows[i]][j] = 1;
					rows2.pb(j);
					int aux = uf.comp(j);
					if(aux!=node){
						apunta[aux] = node;
						uf.join(aux, node);
					}
				} 
			}
		}
		forn(i, sz(rows2)){
			forr(j, rows2[i], n){
				if(!used[rows2[i]][j] && mx[rows2[i]][j] == mini){
					used[rows2[i]][j] = 1;
					int aux = uf.comp(j);
					if(aux!=node){
						apunta[aux] = node;
						uf.join(aux, node);
					}
				} 
			}
		}
	}
	cout << node << '\n';
	forn(i,node) cout << ans[i] << " ";
	cout << '\n';
	int root = -1;
	forn(i,node) if(apunta[i] == -1) root = i;
	cout << root+1 << '\n';
	forn(i,node){
		if(apunta[i]!=-1) cout << i+1 << " " << apunta[i]+1 << '\n';
		
	}
	
	
	
	#ifdef ANARAP
	t1 = clock();double time = (double(t1-t0)/CLOCKS_PER_SEC); cout << "Execution Time: " << time << endl;
	#endif
	return 0;
}

