// Pied!
#include<bits/stdc++.h>
using namespace std;
const int N = 3003;
int n, sub, ts, A[N][N], F[N], C[N], D[N][N];
bool M[N][N], MR[N];
vector < int > Adj[N];
vector < pair < int , int > > E;
void Root(int v, int p, int root)
{
for (int u : Adj[v])
if (u != p)
D[root][u] = D[root][v] + 1, Root(u, v, root);
}
void DFS(int v, int p)
{
int best = -1;
for (int i = 1; i <= n; i ++)
if (MR[i] && A[v][i] == A[p][i] && (best == -1 || D[v][i] < D[v][best]))
best = i;
MR[v] = 1;
if (best == -1)
C[v] = ++ ts;
else
C[v] = C[best];
for (int u : Adj[v])
if (u != p)
DFS(u, v);
}
int main()
{
scanf("%d%d", &sub, &n);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
scanf("%d", &A[i][j]);
memset(F, 63, sizeof(F));
F[1] = 0;
for (int __ = 1; __ <= n; __ ++)
{
int v = 0;
for (int i = 1; i <= n; i ++)
if (!MR[i] && (!v || F[i] < F[v]))
v = i;
bool ff = 0;
for (int i = 1; i <= n && !ff; i ++)
if (MR[i] && A[i][v] == F[v])
E.push_back({i, v}),
Adj[i].push_back(v),
Adj[v].push_back(i),
ff = 1;
MR[v] = 1;
for (int i = 1; i <= n; i ++)
if (!MR[i] && A[v][i] < F[i])
F[i] = A[v][i];
}
memset(MR, 0, sizeof(MR));
for (int i = 1; i <= n; i ++)
Root(i, 0, i);
DFS(1, 0);
for (int i = 1; i <= n; i ++)
printf("%d ", C[i]);
printf("\n");
for (auto X : E)
printf("%d %d\n", X.first, X.second);
return 0;
}
