#include<iostream>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
const int MAXN=3010;
int subtask, n, comInd, arr[MAXN][MAXN], com[MAXN], low[MAXN], tin[MAXN], color[MAXN], par[MAXN], lst[MAXN], tm, ch, cnt;
bool solved[MAXN][MAXN], vis[MAXN];
vector<int> els[MAXN], g[MAXN], st;
void dfs1(int v){
com[v]=comInd;
forn(to, n) if(arr[v][to]==1 && !com[to]) dfs1(to);
}
void dfs2(int v){
tin[v]=low[v]=tm++;
vis[v]=true;
st.PB(v);
forn(to, comInd) if(arr[v][els[to][0]]==2){
if(vis[els[to][0]]) low[v]=min(low[v], tin[els[to][0]]);
else{
dfs2(els[to][0]);
low[v]=min(low[v], low[els[to][0]]);
if(v==els[0][0] || low[els[to][0]]>=tin[v]){
while(!st.empty() && st.back()!=v){
g[st.back()].PB(v);
g[v].PB(st.back());
st.pop_back();
}
}
}
}
}
void dfs3(int v, int p){
par[v]=p;
for(int to:g[v]) if(color[to]!=n && to!=p){
dfs3(to, v);
}
lst[color[v]]=v;
}
void dfs4(int v, int p){
int col=-1;
forn(i, n) lst[i]=-1;
dfs3(v, v);
forn(i, n) if(lst[i]!=-1 && arr[v][lst[i]]==arr[v][par[lst[i]]]) col=i;
if(col==-1) col=cnt++;
color[v]=col;
for(int to:g[v]) if(to!=p) dfs4(to, v);
}
int main(){
scanf("%d", &subtask);
scanf("%d", &n);
forn(i, n) forn(j, n) scanf("%d", &arr[i][j]);
forn(i, n) if(!com[i]) ++comInd, dfs1(i);
forn(i, n) els[com[i]-1].PB(i);
dfs2(els[0][0]);
forn(i, comInd) forsn(j, 1, els[i].size()){
g[els[i][0]].PB(els[i][j]);
g[els[i][j]].PB(els[i][0]);
}
forn(i, n) color[i]=n;
dfs4(0, 0);
forn(i, n) printf("%d ", color[i]+1);
printf("\n");
forn(i, n) for(int j:g[i]) if(j>i) printf("%d %d\n", i+1, j+1);
}
