#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using pii = pair<int, int>;
const int MX = 3e3 + 5;
int pr[MX];
int gp(int n) { return pr[n]?(pr[n]=gp(pr[n])):n; }
void un(int x, int y) {
x=gp(x), y=gp(y);
if (x!=y) pr[y]=x;
}
int T, N, mt[MX][MX], clr[MX], dst[MX][MX];
vector<int> stk;
vector<pii> a;
void dfs(int n, int p) {
if (p) {
pii mn(MX, 0);
for (auto &i:stk) if (mt[i][n]==mt[i][p]) mn=min(mn, pii(dst[i][n], clr[i]));
if (mn.second) clr[n]=mn.second;
else clr[n]=++T;
}else clr[n]=++T;
stk.eb(n);
for (int i=1; i<=N; i++) if (!clr[i]&&gp(i)==i&&mt[i][n]==2) {
for (auto &j:stk) dst[i][j]=dst[j][i]=dst[n][j]+1;
a.eb(n, i);
dfs(i, n);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>T>>N;
for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) {
cin>>mt[i][j];
if (mt[i][j]==1) un(i, j);
}
dfs(gp(1), T=0);
for (int i=1; i<=N; i++) cout<<clr[gp(i)]<<' ';
cout<<'\n';
for (auto &i:a) cout<<i.first<<' '<<i.second<<'\n';
for (int i=1; i<=N; i++) if (gp(i)!=i) cout<<gp(i)<<' '<<i<<'\n';
return 0;
}
