#include <bits/stdc++.h>

using namespace std;

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

  int n;
  cin >> n;
  vector<int> value(n);
  vector<vector<int>> a(n, vector<int>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
    value[i] = a[i][i];
  }

  vector<pair<int, int>> edges;

  function<int(vector<int>)> solve = [&](vector<int> vertices) {
    if (vertices.size() == 1) {
      return vertices[0];
    }

    int mx = -1;
    for (int i = 1; i < (int)vertices.size(); ++i) {
      mx = max(mx, a[vertices[0]][vertices[i]]);
    }

    vector<vector<int>> groups = {{vertices[0]}};
    for (int i = 1; i < (int)vertices.size(); ++i) {
      int g = -1;
      for (int j = 0; j < (int)groups.size(); ++j) {
        if (a[vertices[i]][groups[j][0]] != mx) {
          g = j;
          break;
        }
      }
      if (g == -1) {
        g = (int)groups.size();
        groups.push_back({});
      }
      groups[g].push_back(vertices[i]);
    }

    int root = (int)value.size();
    value.push_back(mx);

    for (auto g : groups) {
      edges.emplace_back(solve(g), root);
    }

    return root;
  };

  vector<int> vertices(n);
  iota(vertices.begin(), vertices.end(), 0);

  int root = solve(vertices);

  cout << value.size() << '\n';
  for (auto v : value) {
    cout << v << ' ';
  }
  cout << '\n' << root + 1 << '\n';
  for (auto [u, v] : edges) {
    cout << u + 1 << ' ' << v + 1 << '\n';
  }

  return 0;
}
