#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 100;
int n, g, mat[N][N], par[N], col[N], cur_col;
set<int> reps;
vector<int> S[N];
vector<pair<int, int>> edges;
bool edge[N][N];
int root(int v){
return (par[v] == -1 ? v : par[v] = root(par[v]));
}
void merge(int u, int v){
if ((u = root(u)) == (v = root(v)))
return;
if (S[u].size() > S[v].size())
swap(u, v);
edges.push_back({u, v});
edge[u][v] = edge[v][u] = 1;
reps.erase(u);
par[u] = v;
for (int x : S[u]){
par[x] = v;
S[v].push_back(x);
}
S[u].clear();
}
int main(){
cin >> g >> n;
for (int i = 1; i <= n; i ++){
par[i] = -1, S[i] = {i};
reps.insert(i);
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
cin >> mat[i][j];
if (g == 2){
col[1] = ++cur_col;
for (int i = 2; i <= n; i ++){
for (int j = i - 1; j > 0; j --){
if (mat[j][i - 1] == mat[j][i]){
col[i] = col[j];
break;
}
}
if (!col[i])
col[i] = ++cur_col;
}
for (int i = 1; i <= n; i ++)
cout << col[i] << " ";
cout << endl;
for (int i = 1; i < n; i ++)
cout << i << " " << i + 1 << endl;
return 0;
}
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
if (mat[i][j] == 1)
merge(i, j);
if (g == 1){
int p = *reps.begin();
for (int v : reps){
col[v] = (p == v) ? 1 : 2;
for (int x : S[v])
col[x] = col[v];
if (p != v) edges.push_back({p, v});
}
}
for (int i = 1; i <= n; i ++)
cout << col[i] << " ";
cout << endl;
for (auto [u, v] : edges)
cout << u << " " << v << endl;
}
