#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1005;
const int maxm = 3e5 + 10;
int a[maxn][maxn], val[maxn];
struct node{
    int x, y, v;
    node(int x = 0, int y = 0, int v = 0): x(x), y(y), v(v){}
}e[maxm];
bool cmp(node a, node b)
{
    if(a.v == b.v)
        return a.x < b.x;
    return a.v < b.v;
}
vector<int> G[maxm];
int f[maxm];
int Find(int x)
{
    if(f[x] == x)
        return x;
    return f[x] = Find(f[x]);
}
int main()
{
    int cnt = 0;
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            scanf("%d", &a[i][j]);
            if(i == j)
                val[i] = a[i][j];
            if(i < j)
                e[++cnt] = node(i, j, a[i][j]);
        }
    }
    int now = n;
    sort(e + 1, e + 1 + cnt, cmp);
    for(int i = 0; i < maxm; i++)
        f[i] = i;
    int pre = 0;
    for(int i = 1; i <= cnt; i++)
    {
        int u = e[i].x;
        int v = e[i].y;
        int num = e[i].v;
        u = Find(u);
        v = Find(v);
        if(u == v)
            continue;
        if(u == pre && num == e[i - 1].v)
        {
            f[v] = now;
            G[now].push_back(v);
        }
        else
        {
            ++now;
            pre = now;
            f[u] = now;
            f[v] = now;
            G[now].push_back(u);
            G[now].push_back(v);
            val[now] = num;
        }
    }
    printf("%d\n", now);
    for(int i = 1; i <= now; ++i)
    {
        printf("%d ", val[i]);
    }
    printf("\n%d\n", Find(1));
    for(int i = 1; i <= now; i++)
    {
        for(int j = 0; j < G[i].size(); j++)
        {
            printf("%d %d\n", G[i][j], i);
        }
    }
}
