#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
int k, n, a[3001][3001], apsp[3001][3001];
int colour[3001], cnt = 1;
bool visited[3001];
vector<int> in_tree;
vector<pair<int, int>> edges;
void dfs(int node = 1) {
visited[node] = true;
in_tree.push_back(node);
FOR(i, 1, n + 1) if (!visited[i] && a[node][i] == 1) {
visited[i] = true;
colour[i] = colour[node];
for (int j : in_tree) apsp[i][j] = apsp[j][i] = apsp[node][j] + 1;
edges.push_back({node, i});
}
FOR(i, 1, n + 1) if (!visited[i] && a[node][i] == 2) {
int mn_same = 0;
for (int j : in_tree) {
apsp[i][j] = apsp[j][i] = apsp[node][j] + 1;
if (a[i][j] == a[node][j] && (!mn_same || apsp[i][j] < apsp[i][mn_same])) mn_same = j;
}
if (mn_same) colour[i] = colour[mn_same];
else colour[i] = ++cnt;
edges.push_back({node, i});
dfs(i);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
FOR(i, 1, n + 1) FOR(j, 1, n + 1) cin >> a[i][j];
colour[1] = 1;
dfs();
FOR(i, 1, n + 1) cout << colour[i] << ' ';
cout << '\n';
for (pair<int, int> i : edges) cout << i.first << ' ' << i.second << '\n';
return 0;
}
