#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (500 + 10), INF = 0x3f3f3f3f3f3f3f3f;
int ind = 0, vecind = 1;
vector<int> vec[N * 2];
int g[N][N], pre[N * 2], val[N * 2];
int fa[N];
int findfa(int x) {
    if (x != fa[x]) fa[x] = findfa(fa[x]);
    return fa[x];
}
void dfs(int x, int u) {
    if (vec[x].size() == 1) {
        pre[vec[x][0]] = u;
        return;
    }
    int maxv = 0;
    for (auto i : vec[x]) {
        fa[i] = i;
        for (auto j : vec[x]) maxv = max(maxv, g[i][j]);
    }
    val[++ind] = maxv;
    pre[ind] = u;
    for (auto i : vec[x])
        for (auto j : vec[x])
            if (g[i][j] < maxv) {
                int a = findfa(i), b = findfa(j);
                if (a != b) fa[a] = b;
            }
    map<int, int> mp;
    for (auto i : vec[x]) {
        if (!mp.count(fa[i])) mp[fa[i]] = ++vecind;
        vec[mp[fa[i]]].push_back(i);
    }
    int indback = ind;
    for (auto i : mp) dfs(i.second, indback);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    ind = n;
    for (int i = 1; i <= n; i++) {
        vec[vecind].push_back(i);
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
            if (i == j) val[i] = g[i][j];
        }
    }
    dfs(vecind, 0);

    cout << ind << "\n";
    for (int i = 1; i <= ind; i++) cout << val[i] << " ";
    cout << "\n";
    cout << n + 1 << "\n";
    for (int i = 1; i <= ind; i++) {
        if (i == n + 1) continue;
        cout << i << " " << pre[i] << "\n";
    }

    return 0;
}