#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
typedef pair <int, int> pii;
const int N = 3e3 + 9;
int n, ind;
vector <pii> ans;
int par[N];
bool del[N];
int col[N];
int dis[N][N];
vector <int> G[N];
int cnt;
int mark[N];
int root (int v) {
return par[v] == v? v: par[v] = root(par[v]);
}
void dfs(int v, int p, int u) {
cnt += !mark[col[v]];
mark[col[v]]++;
if (dis[v][u] < cnt)
assert(false);
if (dis[v][u] > cnt + 1)
assert(false);
if (dis[v][u] == cnt) {
col[u] = min(col[u], col[v]);
mark[col[v]]--;
cnt -= !mark[col[v]];
return ;
}
for (int k: G[v])
if (k != p && col[k] != -1)
dfs(k, v, u);
mark[col[v]]--;
cnt -= !mark[col[v]];
}
void calc(int v, int p = -1) {
col[v] = ind;
if (p != -1)
dfs(p, v, v);
ind += col[v] == ind;
for (int u: G[v])
if (u != p)
calc(u, v);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> dis[i][j];
for (int i = 0; i < n; i++)
par[i] = i, col[i] = -1;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (dis[i][j] == 1 && root(i) != root(j)) {
ans.push_back({root(i), root(j)});
del[root(j)] = true;
par[root(j)] = root(i);
}
for (int i = 0; i < n; i++)
if (del[i] == false)
for (int j = i + 1; j < n; j++)
if (del[j] == false && root(i) != root(j))
if (dis[i][j] == 2) {
ans.push_back({i, j});
G[i].push_back(j);
G[j].push_back(i);
par[root(j)] = root(i);
}
calc(0);
for (int i = 0; i < n; i++)
if (col[i] == -1)
col[i] = col[par[i]];
for (int i = 0; i < n; i++)
cout << col[i] + 1 << " ";
cout << "\n";
for (pii e: ans)
cout << e.first + 1 << " " << e.second + 1 << "\n";
return 0;
}
