#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

int m[510][510];
int p[1510];
int val[1510];

int n;
int k;

const int MAX = 5100;

void solve(vector<int> v,int par, int mx) {
    if(v.size() == 0) return;
    vector<vector<int>> adj(MAX);
    for(int i = 1; i < v.size(); i++) {
        int x = m[v[0]][v[i]];
        adj[x].push_back(v[i]);
    }
    int last = par;
    for(int i = MAX-1; i >= 0; i--) {
        if(adj[i].size() > 0 && i < mx) {
            k++;
            p[k] = last;
            val[k] = i;
            last = k;
        }
        solve(adj[i], k, val[k]);
    }
    p[v[0]] = last;
}
int main() { _
    cin >> n;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        cin >> m[i][j];

    vector<int> v;
    k = n;
    for(int i = 1; i <= n; i++) {
        val[i] = m[i][i];
        v.push_back(i);
    }
    solve(v, INF, INF);

    cout << k << endl;
    for(int i = 1; i <= k; i++) cout << val[i] << " ";
    cout << endl;
    cout << n + 1 << endl;
    for(int i = 1; i <= k; i++) {
        if(i == n+1 )continue;
        cout << i << " " << p[i] << endl;
    }
	exit(0);
}
