#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //int:2*10**9
typedef long double ld;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007 //998244353
#define PI 3.141592653
#define INF 100000000000000 //14
//cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
#define N 510
#define M 5100

vector<ll> salary(M,-1);
vector<vector<ll>> newBridge;
vector<vector<ll>> conn(N,vector<ll>(N));
vector<set<ll>> supSal(N);
vector<vector<ll>> headIndex(N,vector<ll>(5110));
vector<vector<vector<ll>>> supList(N);
ll newEmployee; ll n;

void bfs(ll x, ll prev, ll head, ll headNumber) {
    if (salary[x]!=-1) return;
    salary[x]=conn[x][x];
    // cout << x << " " << head << endl;
    REP(i,n) supSal[x].insert(conn[x][i]);
    REP(i,n) supList[x].pb({conn[x][i],i});
    ll now = x;
    for (auto ite=supSal[x].begin();ite!=supSal[x].end();ite++) {
        if (*ite>head) break;
        if (*ite==conn[x][x]) continue;
        else {
            // cout << x << " " << prev << " " << head << " " << now << " " << newEmployee << " " << *ite << endl;
            if (*ite==head) newBridge.pb({now,headNumber});
            else {
                salary[newEmployee]=*ite;
                newBridge.pb({now,newEmployee});
                now = newEmployee;
                headIndex[x][*ite]=newEmployee;
                newEmployee++;
            }
        }
    }
    auto &v = supList[x];
    sort(v.begin(),v.end());
    for (auto w : v) {
        if (w[1]==x) continue;
        if (w[0]>=head) break;
        else bfs(w[1],x,w[0],headIndex[x][w[0]]);
    }
    return;
}

int main(){
    cin >> n;
    REP(i,n)REP(j,n) cin >> conn[i][j];
    newEmployee = n;
    bfs(0,-1,5100,-1);
    ll cnter = 0; ll maxSal = 0;
    REP(i,M){
        if (salary[i]!=-1) cnter++;
        maxSal = max(maxSal,salary[i]);
    }
    ll syatyo;
    REP(i,M)if(salary[i]==maxSal) syatyo = i;
    cout << cnter << endl;
    REP(i,M) if (salary[i]!=-1) cout << salary[i] << " ";
    cout << endl;
    cout << syatyo+1 << endl;
    for (auto b : newBridge) {
        cout << b[0]+1 << " " << b[1]+1 << endl;
    }
    return 0;
}