#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i,j,n) for(int i=(j);i<=((int)n);++i)
#define rev(i,n,j) for(int i=(n);i>=((int)j);--i)
typedef long long int ll;
#define int long long int
const ll INFL=0x3f3f3f3f3f3f3f3fLL;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
#define endl "\n"
#define mem(a,val) memset(a,val,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define present(container, element) (container.find(element) != container.end())
#define pb push_back
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define readmat(a, n, m) int a[n + 5][m + 5] = {}; rep(i, 1, n) {rep(j, 1, m) cin >> a[i][j];}
#define printmat(a, n, m) rep (i, 1, n) {rep (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define printarr(a, n) rep(i, 1, n) cout << a[i] << " "; cout << endl;
typedef std::map< int,int> mii;
typedef std::vector< int > vi;
typedef std::vector< vi > vvi;
typedef std::pair< int,int > ii;
using namespace std;
const int N = 1e6+5, M = N;
vector<int>g[N];
#define cerr cout
#define cerr cout
#define ts to_string
string ts(char c) { return string(1, c); }
string ts(bool b) { return b ? "true" : "false"; }
string ts(const char* s) { return (string)s; }
string ts(string s) { return s; }
template<class A> string ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
string ts(vector<bool> v) { 
    string res = "{"; for(int i = 0; i < v.size(); ++i) res += char('0' + v[i]);
    res += "}"; return res; }
template<size_t SZ> string ts(bitset<SZ> b) {
    string res = ""; for(int i = 0; i < SZ; ++i) res += char('0' + b[i]);
    return res; }
template<class A, class B> string ts(pair<A,B> p);
template<class T> string ts(T v) { // containers with begin(), end()
    bool fst = 1; string res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> string ts(pair<A,B> p) {
    return "(" + ts(p.first) + ", " + ts(p.second) + ")"; }
 
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
void EDBG(string names) { names = names; }
template<class H, class... T> void EDBG(string names, H h, T... t) {
    auto pos = names.find(',');
    auto first_name = names.substr(0, pos);
    auto rest = names.substr(pos + 1);
    while(rest.front() == ' '){
        rest = rest.substr(1);
    }
    cerr << "[" << first_name << "]: [" << ts(h) << "]" << endl;
    EDBG(rest, t...);
}

#ifdef LOCAL // compile with -DLOCAL
#define error(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define edbg(...) EDBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define error(...) 0
#define edbg(...) 0
#endif

int a[505][505];
int pos;
int n;

int c[N];
int go(vi z)
{
    int x=z.front();
    if (z.size()==1)
    {
        c[x]=a[x][x];
        return x;
    }

    int mx=-INF;

    for(auto &i : z) 
    {
        mx=max(mx,a[x][i]);
    }

    vvi ch;

    ch.push_back({x});
    for(int i = 1; i <z.size(); ++i) 
    {
        int v=z[i];
        int group=-1;
        for(int j = 0; j <ch.size(); ++j) 
        {
            if (a[v][ch[j][0]] != mx) 
            {
                group = j;
                break;
            }
        }

        if (group==-1)
        {
            group=ch.size();
            ch.push_back({});
        }
        ch[group].push_back(v);
    }

    int v=++n;
    for(int i = 0; i <ch.size(); ++i) 
    {
        int u=go(ch[i]);
        g[v].push_back(u);
    }

    
    c[v]=mx;
    return v;
}

void solve()
{
    cin>>n;
    rep(i,1,n)
    {
        rep(j,1,n)
        cin>>a[i][j];
    }

    vi z;
    for(int i = 1; i <=n; ++i) 
    {
        z.push_back(i);
    }
    int root=go(z);
    cout<<n<<endl;
    printarr(c,n);
    cout<<root<<endl;
    for(int i = 1; i <=n; ++i) 
    {
        for(auto &j : g[i]) 
        {
            cout<<j<<" "<<i<<endl;
        }
    }


}



signed main()
{
  FAST;
#ifdef LOCAL
    freopen("C:\\Users\\hp\\Documents\\input.txt", "r", stdin);
    freopen("C:\\Users\\hp\\Documents\\output.txt", "w", stdout);
    std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
    start = std::chrono::high_resolution_clock::now();
#endif

solve();

#ifdef LOCAL
    end = std::chrono::high_resolution_clock::now();
    ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout<<endl;
    cout << "\nElapsed Time: " << elapsed_time << "ms\n";
#endif

return 0;

}

// vector string set map first second continue break return upper_bound lower_bound length void sort
// stack queue pop size erase empty insert
// #Hala BBCF

