#include<bits/stdc++.h>
#define io_o() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fst first
#define scd second
#define endl "\n"
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define REP(i,n) for(int i = 0; i < n; i++)
#define print1d(a) {for(auto v: a) cout << v << " "; cout << endl;}
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int f;
vi ans, parent;
vector<vi> lca;

int dis[5050], sz[5050];

void clear(int i){
    for(int j = 0; j < i; j++){
        dis[j] = j;
        sz[j] = 1;
    }
}

int find(int a){
    if(dis[a] == a) return a;
    else{
        int ans = find(dis[a]);
        dis[a] = ans;
        return ans;
    }
}

bool merge(int a, int b){
    a = find(a), b = find(b);
    if(a == b) return false;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    dis[b] = a;
    return true;
}


int build(vi &ls){
    // cout << "------" << endl;
    // cout << f << endl;
    // print1d(ls);
    // cout << "------" << endl;
    if(ls.size() == 1){
        ans[ls[0]] = lca[ls[0]][ls[0]];
        return ls[0];
    }

    int root = f++;
    int rootVal = 0;
    int n = ls.size();
    
    REP(i, n){
        REP(j, n){
            if(i == j) continue;
            rootVal = max(rootVal, lca[ls[i]][ls[j]]);
        }
    }
    
    clear(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            if(lca[ls[i]][ls[j]] < rootVal) merge(i, j);
        }
    }

    map<int, vi> subtrees;
    for(int i = 0; i < n; i++){
        subtrees[find(i)].pb(ls[i]);
    }
    
    ans[root] = rootVal;
    for(auto p: subtrees){
        parent[build(p.scd)] = root;
    }

    return root;
}

int32_t main(){
    io_o(); 

    int n; cin >> n; vi ls;
    ans.resize(2 * n, -1);
    parent.resize(2 * n, -1);
    lca.resize(n, vi(n));
    f = n;

    REP(i, n){
        REP(j, n){
            cin >> lca[i][j];
        }
        ls.pb(i);
    }
    
    build(ls);
    
    cout << f << endl;
    REP(i, f) cout << ans[i] << " "; cout << endl;
    cout << (n + 1) << endl;

    for(int i = 0; i < f; i++){
        if(i == n) continue;
        cout << (i + 1) << " " << (parent[i] + 1) << endl;
    }

    return 0;
}

