#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=3e3+1;
//int c[N][N];
struct dsu{
int p[N];
dsu(){
iota(p,p+N,0);
}
int get(int v){
return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b,int need=0){
a=get(a),b=get(b);
if(a==b) return 0;
// if(need){
// for(int i=0;i<n;i++)
// assert(c[a][i]==c[b][i]);
// }
p[a]=b;
return 1;
}
}ds;
vec<int> g[N];
int x[N][N];
int clr[N],cnt;
bool can(int a,int b,int v,int p){
if(x[a][v]==x[a][p]){
clr[v]=clr[a];
// cout<<"W "<<clr[v]<<' '<<clr[a]<<' '<<v<<' '<<a<<endl;
// cout<<"W "<<a<<' '<<v<<' '<<a<<' '<<p<<endl;
return 1;
}
for(auto &z : g[a]){
if(z!=b && clr[z])
if(can(z,a,v,p)) return 1;
}
return 0;
}
void dfs(int v,int p){
if(v==p || !can(p,v,v,p))
clr[v]=++cnt;
// cout<<"
for(auto &z : g[v]){
if(z!=p)
dfs(z,v);
}
}
int n;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// ifstream cin("input.txt");
int t;
cin>>t>>n;
vec<pii> e;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cin>>x[i][j];
// for(int j=0;j<n;j++){
// if(c[i][j]==1)
// ds.mg(i,j,1);
// }
}
for(int t=1;t<=2;t++){
for(int v=0;v<n;v++){
for(int u=0;u<n;u++){
if(x[v][u]==t && ds.mg(v,u))
e.pb({v,u}),g[v].pb(u),g[u].pb(v);
}
}
}
dfs(0,0);
for(int i=0;i<n;i++){
cout<<clr[i]<<' ';
}
cout<<'\n';
for(auto &z : e)
cout<<z.f+1<<' '<<z.s+1<<endl;
return 0;
}
/*
*/
