#include<cstdio>
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<vector>
#define me(x,y) memset(x,y,sizeof(x))
#define P pair <int,int>
using namespace std;
const int N = 550;
int a[N][N], vis[N * 10], cnt, fa[N*N], s[N*N], ef[N*N], n, ans;
vector<pair<int, P> >sup;
int find(int x) {
	if (fa[x] == x)return x;
	return find(fa[x]);
}


void construct() {
	sort(sup.begin(), sup.end());
	ans = n;
	for (int i = 0; i < sup.size(); i++) {
		pair<int, P >p = sup[i];
		int val = p.first, dx = find(p.second.first), dy = find(p.second.second);
		if (val == s[dx]) { fa[dy] = dx; ef[dy] = dx; }
		else if (val == s[dy]) { fa[dx] = dy; ef[dx] = dy; }
		else {
			fa[dx] = fa[dy] = ++ans;
			fa[ans] = ans;
			s[ans] = val; ef[dy] = ef[dx] = ans;
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			if (i == j) {
				s[i] = a[i][j];
				fa[i] = i;
			}
			else if (i < j)
				sup.push_back(make_pair(a[i][j], P(i, j)));
		}
	construct();
	printf("%d\n", ans);
	for (int i = 1; i <= ans; i++)printf("%d ", s[i]);
	cout << "\n";
	for (int i = 1; i <= ans; i++)if (find(i) == i) {
		printf("%d\n", i); break;
	}
	for (int i = 1; i <= ans; i++)
		if (ef[i] && ef[i] != i)printf("%d %d\n", i, ef[i]);

}
