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

int mat[505][505];
vector<pair<int, pair<int, int>>> v;
int salary[1005];
int parent[1005];

int get(int a) {
    while(parent[a]) a = parent[a];
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a;
            mat[i][j] = a;
            if (i == j) salary[i] = a;
            else if (i > j) v.push_back({a, {i, j}});
        }
    }

    sort(v.begin(), v.end());

    for (auto e : v) {
        int w = e.first;
        int x = e.second.first;
        int y = e.second.second;
//        cout << "wxy: " << w << " " << x << " " << y << endl;
        x = get(x);
        y = get(y);
        if (salary[x] == w && salary[y] == w) {continue;}
        else if (salary[x] == w) {parent[y] = x;}
        else if (salary[y] == w) {parent[x] = y;}
        else {
            n++;
            parent[x] = n;
            parent[y] = n;
            salary[n] = w;
        }
//        for (int i = 1; i <= n; i++) cout << parent[i] << " ";
//        cout << endl;
    }

    cout << n << "\n";
    for (int i = 1; i <= n; i++) cout << salary[i] << " ";
    cout << "\n";
    cout << n << "\n";
    for (int i = 1; i < n; i++) cout << i << " " << parent[i] << "\n";

    return 0;
}
