#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 3000
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
int aa[N][N];
void dfs(int p, int r, int s, int i) {
int o;
if (s != -1 && aa[r][i] == aa[s][i])
join(r, i);
else
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs(i, r, s == -1 ? j : s, j);
}
}
int main() {
static int ii[N - 1], jj[N - 1];
int n, m, h, i, j, s;
scanf("%d%d", &s, &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &aa[i][j]);
memset(ds, -1, n * sizeof *ds);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
m = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (aa[i][j] == 1 && join(i, j)) {
append(i, j), append(j, i);
ii[m] = i, jj[m] = j, m++;
}
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (aa[i][j] == 2 && join(i, j)) {
append(i, j), append(j, i);
ii[m] = i, jj[m] = j, m++;
}
memset(ds, -1, n * sizeof *ds);
for (i = 0; i < n; i++)
dfs(-1, i, -1, i);
for (i = 0; i < n; i++)
printf("%d ", find(i) + 1);
printf("\n");
for (h = 0; h < n - 1; h++)
printf("%d %d\n", ii[h] + 1, jj[h] + 1);
return 0;
}
