#include <cstring>
#include <iostream>
#include <vector>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;
const int maxn = 505 + 7;
int a[maxn][maxn],vis[maxn];
int b[maxn * maxn];
vector<pair<int,int> >res;
int n;
int dfs(vector<int>&vec) {
    int m = vec.size();
    if(m == 1) return vec[0];
    vector<vector<int> >nex;
    int mx = 0;
    for(int i = 0;i < m;i++) {
        for(int j = i + 1;j < m;j++) {
            mx = max(mx,a[vec[i]][vec[j]]);
        }
    }
    b[++n] = mx;
    int ans = n;
    for(int i = 0;i < m;i++) vis[i] = 0;
    for(int i = 0;i < m;i++) {
        if(vis[i]) continue;
        vector<int>tmp;
        for(int j = 0;j < m;j++) {
            if(vis[j]) continue;
            if(a[vec[i]][vec[j]] != mx) {
                tmp.push_back(vec[j]);
                vis[j] = 1;
            }
        }
        if(tmp.size()) nex.push_back(tmp);
    }
    for(int i = 0;i < nex.size();i++) {
        int pos = dfs(nex[i]);
        res.push_back({pos,ans});
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    int pos = n + 1;
    vector<int>vec;
    for(int i = 1;i <= n;i++) {
        vec.push_back(i);
        for(int j = 1;j <= n;j++) {
            scanf("%d",&a[i][j]);
            if(i == j) b[i] = a[i][j];
        }
    }
    dfs(vec);
    printf("%d\n",n);
    for(int i = 1;i <= n;i++) {
        printf("%d",b[i]);
        if(i == n) printf("\n");
        else printf(" ");
    }
    printf("%d\n",pos);
    for(int i = 0;i < n - 1;i++) printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}
