#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<bitset>
#include<cstring>
#include<algorithm>
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int n,a[600][600],fa[maxn],val[maxn];
struct node{
    int u,v,val;
}e[maxn];
bool cmp(node a,node b){
    if(a.val == b.val){
        return a.u < b.u;
    }
    return a.val < b.val;
}
set<pair<int , int>> ans;
set<int> se;
int find(int x){
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void conbine(int u,int v){
    int temp1 = find(u);
    int temp2 = find(v);
    if(temp1 < temp2) swap(temp1,temp2);
    if(temp1 != temp2){
        fa[temp2] = temp1;
    }
}
int main(){
    scanf("%d",&n);
    int cnt = 0;
    for(int i = 1; i <= n * n; i ++){
        fa[i] = i;
    }
    for(int i = 1; i <= n ; i ++){
        for(int j = 1; j <= n; j ++){
            scanf("%d",&a[i][j]);
            if(i < j) e[++cnt] = {i , j , a[i][j]};
            if(i == j) val[i] = a[i][j];
        }
    }
    sort(e + 1,e + cnt + 1,cmp);
    for(int i = 1; i <= cnt; i ++){
        int u = e[i].u,v = e[i].v,w = e[i].val;
        u = find(u),v = find(v);
        if(u == v) continue;
        if(val[u] == w){
            fa[v] = u;
            ans.insert({v,u});
        }
        else if(val[v] == w){
            fa[u] = v;
            ans.insert({u,v});
        }
        else{
            val[++n] = w;
           // se.insert(w);
            conbine(n,u);
            conbine(n,v);
            ans.insert({u,n});
            ans.insert({v,n});
        }

    }
    printf ("%d\n",n);
    for(int i = 1; i <= n; i ++){
        printf ("%d ",val[i]);
    }
    printf ("\n");
    printf ("%d\n",n);
    for(auto p : ans){
        printf ("%d %d\n",p.first,p.second);
    }

}
