#include <bits/stdc++.h>
#define forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fst first
#define snd second

#ifdef ANARAP
#else
#endif

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

int main()
{
	#ifdef ANARAP
		freopen("input.in", "r", stdin);
		//freopen("output.out", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	vector<vector<int>> vv(n, vector<int>(n));
	map<int, set<int>> g;
	int nxtid = n;
	vector<int> rowId(n);
	forn(i,n) rowId[i] = i;
	const int INF = 1000100;
	map<int, vector<ii>> m;
	map<int,int> salaryOf;
	forn(i,n)forn(j,n)
	{
		cin >> vv[i][j];
		if(i <= j) m[vv[i][j]].pb(mp(i,j));
	}
	while(!m.empty())
	{
		int r = -1, c = -1;
		bool done = false;
		while(!m.empty() && !done)
		{
			while(!m.empty() && (m.begin()->snd.empty())) m.erase(m.begin());
			if(m.empty()) break;
			r = m.begin()->snd.back().fst;
			c = m.begin()->snd.back().snd;
			m.begin()->snd.pop_back();
			if(vv[r][c] != INF) done = true;
		}
		if(m.empty()) break;
		assert(done);
		assert(r != -1);
		if(r == c)
		{
			salaryOf[r] = vv[r][c];
			vv[r][c] = INF;
			continue;
		}
		int newnode = nxtid++;
		salaryOf[newnode] = vv[r][c];
		set<int> auxnodes;
		assert(r < c);
		forn(k,n) if(vv[r][k] == vv[r][c] || vv[k][c] == vv[r][c]) auxnodes.insert(k);
		forall(it,auxnodes)
		{
			g[newnode].insert(rowId[*it]);
			rowId[*it] = newnode;
		}
		forall(i,auxnodes)forall(j,auxnodes) if(i!=j)
		{
			assert(vv[*i][*j] == salaryOf[newnode] || vv[*i][*j] == INF);
			vv[*i][*j] = vv[*j][*i] = INF;
		}
	}
	cout << nxtid << '\n';
	assert(sz(salaryOf) == nxtid);
	forall(it, salaryOf) cout << it->snd << ' ';
	cout << '\n' << nxtid << '\n';
	forall(it, g) forall(it2, it->snd) cout << *it2+1 << ' ' << it->fst+1 << '\n';
	return 0;
}
