#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <deque>
#include <ctype.h>
#include <limits.h>
#include <map>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <random>

using namespace std;
typedef long long ll;

void solve();

mt19937 rng(time(0));

ll qpow(ll x, ll p, ll MOD) {
    ll res = 1, v = x;
    while (p) {
        if(p & 1) {
            res *= v;
            res %= MOD;
        }
        v *= v;
        v %= MOD;
        p >>= 1;
    }
    return res;
}

ll inv(ll x, ll MOD) {
    return qpow(x, MOD - 2, MOD);
}

void init() {
#ifdef _LOCAL_ 
    if(!freopen("case.txt", "r", stdin)) {
        perror("open file failed!:");
        exit(1);
    }
    if(!freopen("main.ans", "w", stdout)) {
        perror("open file failed!:");
        exit(1);
    }
#endif
}
 
#ifdef _LOCAL_
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#   define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#   define dbg(...)
#endif

ll read() {
    int ch = getchar();
    if(ch == EOF) {
        return INT_MIN;
    }
    while(!isdigit(ch) && ch != '-') {
        ch = getchar();
        if(ch == EOF) {
            return INT_MIN;
        }
    }
    ll res = 0, sign = 1;
    if(ch == '-') {
        ch = getchar();
        sign = -1;
    }
    while(isdigit(ch)) {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * sign;
}

int main() {
    init();
    solve();
    return 0;
}
/** 写之前 : 
 *  1. MAXN 是否定义正确？
 */
/*********************code start here*********************/
int a[505][505];
int sa[1100] = {0}, fa[1100];
void solve() {
    int n = read();
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            a[i][j] = read();
        }
    }
    memset(fa, -1, sizeof(fa));
    int sz = n;
    for(int i = 0; i < n; ++i) {
        sa[i] = a[i][i];
        for(int j = i+1; j < n; ++j) {
            if(fa[j] == -1) {
                int p = i;
                while(fa[p] != -1 && sa[fa[p]] < a[i][j]) {
                    p = fa[p];
                }
                if(fa[p] == -1) {
                    fa[p] = sz++;
                    sa[fa[p]] = a[i][j];
                }
                if(sa[fa[p]] == a[i][j]) {
                    fa[j] = fa[p];
                } else {
                    int up = fa[p];
                    fa[j] = fa[p] = sz++;
                    fa[fa[p]] = up;
                    sa[fa[p]] = a[i][j];
                }
            } else {
                int ti = i, tj = j;
                while(sa[fa[ti]] < a[i][j]) {
                    ti = fa[ti];
                }
                while(sa[fa[tj]] < a[i][j]) {
                    tj = fa[tj];
                }
                if(sa[fa[ti]] == a[i][j]) {
                    fa[tj] = fa[ti];
                } else if(sa[fa[tj]] == a[i][j]) {
                    fa[ti] = fa[tj];
                } else {
                    int up = fa[ti];
                    fa[ti] = fa[tj] = sz++;
                    fa[fa[ti]] = up;
                    sa[fa[ti]] = a[i][j];
                }
            }
        }
    }
    printf("%d\n", sz);
    for(int i = 0; i < sz; ++i) {
        printf("%d ", sa[i]);
    }
    printf("\n");
    for(int i = 0; i < sz; ++i) {
        if(fa[i] == -1) {
            printf("%d\n", i + 1);
            break;
        }
    }
    for(int i = 0; i < sz; ++i) {
        if(fa[i] != -1) {
            printf("%d %d\n", i + 1, fa[i] + 1);
        }
    }
}

/** 提交前检查 : 
 *  1. 答案和中间结果是否应该是 ll?
 *  2. 是否还有没有读入的数据？
 *  3. 是否有 n = 1 的情况？
 */