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

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

struct dsu{
    int n; vector<int> sz, par;
    void init(int _n){
        n = _n; sz.resize(n); par.resize(n);
        F0R(i, n) sz[i] = 1, par[i] = i;
    }
    int find(int x){ return par[x] = ( x == par[x] ? par[x] : find(par[x])); }
    void comb(int a, int b) {
        a=find(a); b=find(b);  
        if(a!=b) {sz[a]+=sz[b]; par[b] = a; }
    }
};
#undef D
#define D QWERWQWEQWEQWEQ
dsu D;
    set<ar<int, 3>> pq;

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<vi> a(n, vi(n));
    vi par(n*10);
    D.init(10*n);
    vector<int> ans(10*n);
    int cnt = n;
    F0R(i, n){
        F0R(j, n){
            cin >> a[i][j];
            if(i<=j)
            pq.insert(ar<int, 3>{a[i][j], i, j});
        }
    }
    while(!pq.empty()){
        ar<int, 3> t = *pq.begin(); pq.erase(t);
        if(t[1]==t[2]){
            ans[t[1]] = t[0];
        }
        else{                
            int u = D.find(t[1]), v = D.find(t[2]);
            if(t[0]==ans[u]) par[v] = u, D.comb(u, v);
            else if(t[0]==ans[v]) par[u] = v, D.comb(v, u);
            else {
                ans[cnt] = t[0];
                par[u]=cnt;
                par[v]=cnt;
                D.comb(cnt, u);
                D.comb(cnt, v);
                cnt++;
            }
        }
    }
    cout << cnt << nl;
    F0R(i, cnt){
        cout << ans[i] << ' ';
    }
    cout << nl;
    cout << cnt << nl;
    F0R(i, cnt-1){
        cout << i+1 << ' ' << par[i]+1 << nl;
    }
    return 0;
}