#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 105;

const ll mod = 998244353;//1e9+7;

ll lcas[505][505];

vector<vector<int>> g;

vector<ll> c;
int n;

int buildTree(const vector<int>& mask) {
    vector<vector<int>> bins;
    vector<int> binPresenter;
    ll maxLca = 0;

    for (int i=0;i<n;i++) {
        if (!mask[i]) continue;
        for (int j=i+1;j<n;j++) {
            if (!mask[j]) continue;
            maxLca = max(maxLca, lcas[i][j]);
        }
    }

    for (int i=0;i<n;i++) {
        if (!mask[i]) continue;
        bool wasBinFound = false;
        for (int j=0;j<bins.size();j++) {
            int lca = lcas[i][binPresenter[j]];
            if (lca!=maxLca) {
                wasBinFound = true;
                bins[j][i] = 1;
            }
        }
        if (!wasBinFound) {
            bins.push_back(vector<int>(n,0));
            bins.back()[i] = 1;
            binPresenter.push_back(i);
        }
    }
    if (bins.size() == 1) {
        assert(maxLca==0);
        for (int i=0;i<n;i++) {
            if (!mask[i]) continue;
            c[i] = lcas[i][i];
            return i;
        }
    }
//    for (int i=0;i<bins.size();i++) {
//        cout << "binPresenter: " << binPresenter[i]+1 << ", mask: ";
//        for (auto& it: bins[i]) {
//            cout << it << " ";
//        }
//        cout << endl;
//    }
    vector<int> roots;
    for (int i=0;i<bins.size();i++) {
        int root = buildTree(bins[i]);
        roots.push_back(root);
    }
    c.push_back(maxLca);
    g.push_back(roots);
//    cout << "vertex: " << ((int) g.size()) << endl;
//    for (auto& it: roots) {
//        cout << it+1 << " ";
//    }
//    cout << endl;
    return ((int) g.size())-1;

}
void solve() {
    cin >> n;
    g.resize(n);
    c.resize(n);
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            cin >> lcas[i][j];
        }
    }
    int root = buildTree(vector<int>(n, 1));
    assert(root+1==g.size());
    int k = g.size();
    cout << k << "\n";
    for (int i=0;i<k;i++) {
        cout << c[i] << " ";
    }
    cout << "\n";
    cout << root+1 << "\n";
    for (int i=0;i<k;i++) {
        for (auto& it: g[i]) {
            cout << it+1 << " " << i+1 << "\n";
        }
    }
}

int main() {
    //freopen("input.txt","r",stdin);
    int t = 1;
//    cin >> t;
    for (int i=0;i<t;i++)
    solve();
    return 0;
}
