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

typedef long long LL;
typedef pair<int, int> pii;

const int N = 1000+19;

int g[N][N],sa[N];
vector<int> son[N];
int n,rt,now;

void dfs(const vector<int> &tr, int rt) {
  int val = 0;
  for(auto v : tr) for(auto u : tr)
    val = max(val,g[u][v]);
  sa[rt] = val;
  int num = tr.size();
  vector<int> vis(num);
  for(int i = 0 ; i < num ; ++i) if(!vis[i]) {
    vector<int> nb;
    for(int j = 0 ; j < num ; ++j) {
      int u = tr[i],v = tr[j];
      if(g[u][v] != val) {
        vis[j] = 1;
        nb.push_back(v);
      }
    }
    if(nb.size() == 1) son[rt].push_back(tr[i]);
    else {
      ++now;
      son[rt].push_back(now);
      dfs(nb,now);
    }
  }
}

void output(int rt) {
  for(auto v : son[rt]) {
    output(v);
    cout << v << ' ' << rt << endl;
  }
}

void solve(int ID) {
  cin >> n;
  for(int i = 1 ; i <= n ; ++i) {
    for(int j = 1 ; j <= n ; ++j) 
      cin >> g[i][j];
    sa[i] = g[i][i];
  }
  vector<int> tree;
  for(int i = 1 ; i <= n ; ++i) tree.push_back(i);
  rt = n+1;
  now = rt;
  dfs(tree,rt);
  cout << now << endl;
  for(int i = 1 ; i <= now ; ++i) cout << sa[i] << ' ';cout << endl;
  cout << rt << endl;
  output(rt);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int T = 1;
  //cin >> T;
  
  for (int i = 1 ; i <= T ; ++i) {
    solve(i);
  }
  return 0;
}