#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define pb push_back
#define ll long long int
# define pll pair<ll,ll>
#define sec second
#define ft first
#define mp make_pair
# define fio ios_base::sync_with_stdio(false); cin.tie(NULL)
int a[509][509];
vector <pair<int,int> >  v ;
pair<int,int>p[1009];
int lca[509][509];
bool vis[1009] = {false};
int c[1009];
int cnt;
int main()
{
    int n;
    cin >> n ;
    cnt = n ;
    for(int i = 1 ; i <= n ; i++)
    {
        v.clear();
        for(int j = 1 ; j <= n ;j++)
    {
        cin >> a[i][j];
        v.pb({a[i][j],j});
    }
        sort(v.begin(),v.end());
        
        for(int k = 1 ; k < v.size(); k++)
        {
           
                if( v[k].ft != v[k-1].ft)
                {
                    if(v[k].sec >= i)
                    {
                    cnt++;
                    //cout << i << " " << v[k].sec << " " << cnt <<"\n";
                    c[cnt] = v[k].ft ;
                    if(k!=1)    p[cnt-1] = mp(cnt,v[k].ft);
                    else p[i] = mp(cnt,v[k].ft);
                    lca[i][v[k].sec] =lca[v[k].sec][i]=cnt;
                    }
                    else
                    {
                        if(k!=1)    p[cnt] = mp(lca[v[k].sec][i],v[k].ft);
                        else p[i] = mp(lca[v[k].sec][i],v[k].ft);
                        break;
                    }
                    
                }
                else lca[v[k].sec][i] = lca[i][v[k].sec] = cnt ;
            
        }
    }
    //cout << lca[6][3]<<"\n";
    for(int i = 1 ; i <= n ; i++) c[i] = a[i][i];
    int maxval = -1 , maxx = -1 ;
    for(int i = 1 ; i <= cnt ; i++)
    {
        if(c[i] > maxval) {
            maxval = c[i];
            maxx = i ;
        }
    }
    cout<<cnt<<"\n";
    for(int i = 1 ; i <= n ; i++) cout << a[i][i]<<" ";
    for(int i = n+1 ; i <= cnt ; i++) cout << c[i] <<" " ;
    cout <<"\n";
    cout << maxx<<"\n";
    for(int i = 1 ; i <= cnt ; i++)
    {
        if(maxx!=i)cout << i << " " << p[i].ft <<"\n";
    }
   // for(int i = 1 ; i <= cnt ; i++) cout <<p[i].ft<<" "<<p[i].sec<<"\n";
    
}
