#include <iostream>
#include <vector>
using namespace std;
const int N = 3e3 + 10;
int a[N][N];
int par[N];
vector<int> vec[N];
int root(int v){
if (par[v] == 0)
return v;
return par[v] = root(par[v]);
}
void solve1(int n){
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i != j and a[i][j] == 1 and root(i) != root(j))
par[root(i)] = root(j);
for (int i=1;i<=n;i++)
cout<<1 + (root(i) != root(1))<<' ';
cout<<'\n';
for (int i=2;i<=n;i++)
vec[root(i)].push_back(i);
for (int i=1;i<=n;i++){
int prv = 1;
for (int j : vec[i])
cout<<prv<<" "<<j<<'\n', prv = j;
}
}
int main(){
int t, n;
cin>>t>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>a[i][j];
if (t == 1)
solve1(n);
}
