#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10,M=10010;

struct node {
    int a1,a2,val;
}w[N];
int tot;
bool cmp(node a,node b) {
    if(a.val==b.val) {
        if(a.a1==b.a1) return a.a2<b.a2;
        return a.a1<b.a1;
    }
    return a.val<b.val;
}

int c[M],num;
int fa[M],f[M];
int findfa(int x) {
    if(fa[x]!=x) fa[x]=findfa(fa[x]);
    return fa[x];
}

int main() {
    // freopen("test.in","r",stdin);
    int n;
    tot=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) {
            int p;
            scanf("%d",&p);
            if(i==j) c[i]=p;
            if(i<j) {
                node tmp;
                tmp.a1=i;
                tmp.a2=j;
                tmp.val=p;
                w[++tot]=tmp;
            }
        }
    sort(w+1,w+tot+1,cmp);
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) fa[i]=i;
    num=n;
    for(int i=1;i<=tot;i++) {
        int a1=w[i].a1,a2=w[i].a2,val=w[i].val;
        int f1=findfa(a1),f2=findfa(a2);
        if(c[f1]==val) {
            fa[f2]=f1;
            f[f2]=f1;
            continue;
        }
        if(c[f2]==val) {
            fa[f1]=f2;
            f[f1]=f2;
            continue;
        }
        c[++num]=val;
        fa[f1]=num;
        f[f1]=num;
        fa[f2]=num;
        f[f2]=num;
        fa[num]=num;
    }
    cout<<num<<'\n';
    for(int i=1;i<=num;i++) cout<<c[i]<<" "; cout<<'\n';
    int rt;
    for(int i=1;i<=num;i++) if(findfa(i)==i) rt=i;
    cout<<rt<<'\n';
    for(int i=1;i<=num;i++) {
        if(findfa(i)==i) continue;
        cout<<i<<" "<<f[i]<<'\n';
    }
    return 0;
}