/*    Author - Satwik_Tiwari  */

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()
#define minheap priority_queue <ll, vector<ll>, greater<ll>>
//#define endl "\n"
#define mem(a , b) memset(a , b , sizeof(a))
#define itos to_string

#define debug(a) cerr << #a << ": "; _print(a); cerr << endl;
#define debugarr(a,n) cerr << #a << ": "; _print(a,n); cerr << endl;

typedef unsigned long long ull;
typedef long double ldb;

void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(ldb t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template<class T> void _print(deque <T> deq) {cerr << "[ "; for (T i : deq) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
void _print(int a[],int n) {cerr << "[ "; for(int i=0;i<n;i++){_print(a[i]); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

int power(int x, int y, int M) {int res = 1; while (y > 0) {if (y & 1) res = (res * x) % M; y >>= 1; x = (x * x) % M;} return res % M;}
int power(int x, int y) {int res = 1; while (y > 0) {if (y & 1) res = (res * x); y >>= 1; x = (x * x);} return res;}
const int mxn = 501 + 6 ; int t, mod = 1000000007, inf = power(10, 18);
int n;
vector<vector<int>> a(mxn,vector<int>(mxn));
vector<int> g[mxn * 10];
vector<int> val(mxn*10);
int nodes = n;

void rec(int whichnode, vector<int> have){
//    debug(whichnode); debug(have);
    nodes = max(whichnode,nodes);
    int mx = 0;
    for(int i=0;i<have.size();i++){
        for(int j = i+1;j<have.size();j++){
            mx = max(mx,a[have[i]][have[j]]);
        }
    }
    val[whichnode] = mx;
    if(have.size() <= 2) {
        g[whichnode].push_back(have[0]);
        g[whichnode].push_back(have[1]);
        return;
    }

    vector<int> grps (have.size(),-1);
    int curr = 1;
    for(int i=0;i<have.size();i++){
        if(grps[i] != -1) continue;
        grps[i] = curr; curr ++ ;
        for(int j=i+1;j<have.size();j++){
            if(a[have[i]][have[j]] != mx){
                grps[j] = grps[i];
            }
        }
    }
//    debug(grps);
    vector<int> temp;
    for(int i=1;i<curr;i++){
        temp.clear();
        for(int j=0;j<have.size();j++){
            if(grps[j] == i) temp.push_back(have[j]);
        }
//        debug(temp);
        if(temp.size() == 1){
            g[whichnode].push_back(temp[0]);
        }
        else {
            nodes ++;
            g[whichnode].push_back(nodes);
            rec(nodes, temp);
        }
    }
}

void test_case() {
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }

    for(int i=0;i<n;i++) val[i] = a[i][i];
    vector<int> have;
    for(int i=0;i<n;i++){have.push_back(i);}
    rec(n,have);

    cout << nodes + 1 << endl;
    for(int i=0;i<=nodes;i++){
        cout << val[i] << " " ;
    }
    cout << endl << n + 1 << endl;
    for(int i=0;i<=nodes;i++){
        for(int j: g[i]){
            cout << j+1  << " " << i+1 << endl;
        }
    }
}

int32_t main() {
    FastIO;
    t = 1;
    // cin >> t;
    int casee = 1;
    while (t--) {
        // cout << "Case #" << casee << ": " ;
        test_case();
        casee++;
    }
    return 0;
}

